Доказательство. На интервале (xт-Δ,xт+Δ) существует только 1 корень уравнения (2)

Утверждение 3.

На интервале (x_т-Δ,x_т+Δ) существует только 1 корень уравнения (2).

Пусть существует 2 корня x₁ и x₂≠x₁, тогда в силу (4) x₁=φ(x₁), x₂=φ(x₂). Из (6) следует | x₂-x₁|=|φ(x₂)-φ(x₁)|≤q|x₂-x₁|, т.е. |x₂-x₁|≤q|x₂-x₁|. Из этого следует, что q= 1, а это противоречит (7). Следовательно, корень только 1.

█

Следует так же отметить, что если φ(x) имеет на интервале (x_т-Δ,x_т+Δ) непрерывную производную, то (6) выполняется, когда

|φ′(x)|≤q => |φ′(x)|< 1для xÎ(x_т-Δ,x_т+Δ). (11)

Если |φ′(x_т)|< 1, x₀Î(x_т-Δ,x_т+Δ), то итерации сойдутся. Если |φ′(x_т)|> 1, то в силу непрерывности производной |φ′(x)|> 1 и на некотором интервале (x_т-Δ₁,x_т+Δ₁), поэтому итерации не сойдутся к корню. Если же |φ′(x_т)|< 1, но x₀Ï(x_т-Δ,x_т+Δ), т.е. |φ′(x₀)|> 1, то в данном случае о сходимости процесса можно судить только после дополнительного анализа функции φ(x).

Как и при поиске решения методом дихотомии будем считать задачу выполненной, если найденное некоторое значение x_чÎ[x_т-ε,x_т+ε], где ε – заданная точность. Для определения того, когда можно прекратить итерации, т.е. когда достигнута заданная точность, подробнее рассмотрим неравенство (9). По сути, нам необходимо добиться выполнения следующего неравенства:

|x_n+1-x_т| ≤ ε, (12)

а в силу того, что из (9) можно получить неравенство |x_n+1-x_т| ≤ qⁿ⁺¹|x₀-x_т|, где q можно определить как для любого целого n≥1, выведем условие достижения заданной точности (12). Введём обозначения δ_n+1=|x_n+1-x_т|. Из (9) , а так же очевидно, что δ₀-δ_n+1=|x₀-x_n+1|=ξ, тогда:

δ₀=δ_n+1+ξ

δ_n+1=gδ=g(δ_n+1+ξ)

. (13)

Неравенство (13) является условием остановки процесса итераций, т.е. условием достижения заданной точности. В завершение рассмотрения данного метода остаётся только построить блок-схему его алгоритма. Будем считать, что |φ′(x_т)|<1, x₀Î(x_т-Δ,x_т+Δ).

Метод касательных (Ньютона)

Метод Ньютона называют также методом касательных и методом линеаризации. Суть метода заключается в том, что в точке приближения к функции строится касательная (Рис. 3). Следующая точка приближения – это точка пересечения полученной прямой с осью Ox. Процесс продолжается вплоть до достижения заданной точности.

Из рисунка очень легко получить итерационную формулу метода, используя геометрический смысл производной. Если f(x) имеет непрерывную производную f’(x)≠0, тогда получим

Аналогично получаем x₂, x₃, и т.д. Таким образом, можем записать общую формулу:

Метод Ньютона можно рассматривать, как частный случай метода простых итераций, если задать . В этом случае . Условие сходимости метода простых итераций можно переписать для метода Ньютона следующим образом:

(14)

Рассуждения по поводу выбора начального приближения в методе Ньютона такие же, как и в методе простых итераций, только вместо (11) используется (14). Для данного метода также применимо (13). Напишем блок-схему алгоритма метода Ньютона.

Метод секущих

В данном методе, в отличие от метода Ньютона, проводятся не касательные, а секущие (Рис. 4). Из рисунка легко получить итерационную формулу:

. (15)

В качестве начального приближения необходимо задать не только x₀, но и x₁. Метод секущих имеет одно преимущество перед методом Ньютона – здесь не нужно вычислять производную. Но этот метод имеет также существенные недостатки. Сходимость итераций может быть немонотонной не только вдали от корня, но и в малой окрестности корня.

В знаменателе формулы (15) стоит разность значений функции. Вдали от корня это не существенно; но вблизи корня, особенно корня высокой кратности, значения функции малы и очень близки. Возникает потеря значащих цифр, приводящая к «разболтке» счёта. Это ограничивает точность, с которой можно найти корень; для простых корней это ограничение не велико, а для кратных может быть существенным.

От «разболтки» страхуются так называемым приёмом Гаврика. Выбирают не очень малое ε, ведут итерации до выполнения условия |x_n+1-x_n|<ε и затем продолжают расчёты до тех пор, пока |x_n+1-x_n| убывают. Первое же возрастание обычно означает начало «разболтки»; тогда расчёт прекращают и последнюю итерацию не используют.

Все ограничения по сходимости итераций для данного метода такие же, как и в методах простых итераций и Ньютона. А вот определение достижения заданной точности, как видно из описания метода, затруднительно, и, даже, возможна ситуация, когда из-за «разболтки» счёта заданная точность не будет достигнута никогда.

При использовании метода секущих в явном виде определить точность трудно, поэтому используют косвенный метод. Считают, что вблизи корня |x_n+1-x_n|~|x _т -x_n+1|. Конечно эта оценка весьма примерна, но при больших n (в идеале при n→∞) это так и есть. Построим блок-схему алгоритма данного метода с использованием приёма Гаврика.

Численные методы вычисления определённых интегралов

Метод левых прямоугольников

Эти методы численного интегрирования основываются на геометрическом смысле интеграла. Как известно интеграл есть площадь криволинейной трапеции ограниченной подынтегральной функцией f(x) на отрезке [a,b]. Для вычисления интеграла I отрезок [a,b] разбивают на n отрезков длиной h. На каждом отрезке криволинейную трапецию приближают прямоугольником, так как его площадь можно легко вычислить. Затем суммируют все полученные площади, получая тем самым приближённое значение интеграла.

На рис. 5 проиллюстрирован, так называемый, метод левых прямоугольников. Его название объясняется тем, что высота прямоугольника f(x) вычисляется в левой границе отрезка h. Выведем формулу для приближённого вычисления интеграла I.

Как видно из рисунка площадь первого слева прямоугольника S₀=f(x₀)h. Площадь следующего S₁=f(x₁)h. Легко заметить, что площадь i -го прямоугольника S_i=f(x_i)h. Всего таких прямоугольников n, нумерация их ведётся от 0 до n -1. Таким образом, приближённое значение интеграла, полученное этим методом, вычисляется по формуле:

. (16)

Оценим погрешность формулы (16) на отрезке [x_i,x_i+h]. Для этого разложим функцию f(x) по формуле Тейлора, выбирая x_i за центр разложения и предполагая наличие у функции требуемых по ходу рассуждений непрерывных производных.

f(x)=f(x_i)+(x-x_i)f’(x_i)+… (17)

В формуле (17) для определённости отбросим члены, содержащие производные высших порядков, т.е. 2-ю и выше. Тогда получим:

, т.е.

(18)

Чтобы получить общую погрешность метода на отрезке [a,b] просуммируем все R_Лi:

(19)

Поскольку в (17) были отброшены члены, содержащие более высокие степени длины интервала, то выражение остаточного члена (19) является асимптотическим, т.е. выполняющимся при h→0 с точностью до членов более высокого порядка малости. Но для справедливости этой оценки необходимо существование непрерывной f’(x); если f’(x) кусочно-непрерывна, то удаётся сделать лишь мажорантную оценку

(20)

Эту формулу можно записать иначе

, (21)

где n – количество отрезков, на которые разбит отрезок [a,b].

Перед началом вычислений по данному методу необходимо определиться с h или, что, по сути, то же самое, с n. Пусть известны границы отрезка [a,b], задана подынтегральная функция f(x) и точность ε, с которой должен быть вычислен интеграл. Чтобы определить h и n воспользуемся простым и очевидным неравенством:

|R_Л|≤ε,(22)

откуда получаем для непрерывной f’(x):

(23)

либо если учесть, что получим

. (24)

Для кусочно-непрерывной f’(x) с учётом (20) и (21) справедливо следующее

(25)

(26)

Метод правых прямоугольников

Этот метод похож на предыдущиу. Отличие в том, что высота прямоугольников вычисляется по правой границе (Рис. 6).

Выводы формул для данного метода аналогичны предыдущему. Основные отличия заключаются в нумерации. Формула метода правых прямоугольников выглядит следующим образом:

. (27)

Рассуждения и конечные формулы, связанные с определением погрешности метода и выбором ширины основания прямоугольников аналогичны тому, что получено в предыдущем методе.

Метод средних прямоугольников

Чтобы уменьшить погрешность методов левых и правых прямоугольников был предложен метод средних, т.е. метод в котором высота прямоугольника вычисляется в середине отрезка h (Рис. 7). Обращаясь к рисунку легко увидеть, что площади прямоугольников вычисляются по следующим формулам:

(28)

Оценим погрешность формулы (28) на отрезке [x_i,x_i+h]. Прежде всего, получим разложение по формуле Тейлора для данного метода. Центр разложения в данном случае будет точка . Тогда получим:

(29)

В формуле (29) отбросим члены, содержащие 3-ю и выше производные. Получаем:

I_i-I_Ср.i=R_Ср.i

, т.е.

. (30)

Аналогично тому, как были получены формулы (20), (21), (23), (24), (25) можно получить формулы, по которым оцениваются n и h, для данного метода. Запишем окончательные формулы для непрерывной f’’(x).

(31)

(32)

Для кусочно-непрерывной f’’(x) получаем мажорантные оценки:

(33)

(34)

Сравнивая формулы (19) и (30) погрешностей методов приходим к выводу, что погрешность метода средних во много раз ниже погрешности метода левых или правых прямоугольников, т.е. метод средних во много раз точнее и для достижения заданной точности требует меньше машинного времени. Поэтому блок-схему построим именно для метода средних.

Введём обозначение. [n] – целая часть n, полученная путём отбрасывания дробно части. Для вычисления интеграла дано ε, [a,b], f(x), f’’(x). Прежде всего, через ε необходимо получить n. Пользоваться формулой (32) мы не будем, т.к. в ней необходимо вычислять интеграл. Воспользуемся мажорантной оценкой (34). Для этого перед вычислением интеграла необходимо найти , но это легко осуществимо с помощью небольшого циклического процесса. Для него понадобиться знание количества разбиений , на которых будем вычислять значения второй производной. Обозначим это количество n₁.

Метод трапеций

Метод трапеций основан на том, что криволинейная трапеция приближается прямолинейной (Рис. 8). Т.е. площади вычисляются по следующей формуле:

Таким образом, получаем общую формулу трапеций:

. (35)

Теперь оценим погрешность метода. Вывод формулы погрешности аналогичен выводу (30), поэтому приведём сразу окончательную оценку погрешности для непрерывной f’’(x):

; (36)

для кусочно-непрерывной f’’(x):

(37)

Оценивая n и h, получим:

(38)

(39)

Для кусочно-непрерывной f’’(x):

(40)

(41)

Как видно из полученных формул погрешность метода средних примерно вдвое меньше погрешности метода трапеций. Очевидно, что если функция определена на всём интервале, лучше пользоваться методом средних, метод трапеций используют обычно для функций определённых только в узлах сетки.

Знаки главного члена погрешности у формул трапеций и средних разные. Поэтому, если есть расчёты по обеим формулам, то точное значение интервала лежит, как правило, в вилке между ними. Деление этой вилки как 2:1 даёт уточнённый результат близкий к тому, который получается при использовании более точного метода Симпсона.

Метод Симпсона

Этот метод основан на том, что функция f(x) приближается на отрезке [x_i-h, x_i+h] параболой (причём x_i отстоит от x_i+1 на расстоянии 2h) (Рис.9). То есть через заданные точки проводится парабола. Но известно, что уравнение параболы имеет вид ρ(x)=ax²+bx+c, т.е. чтобы определить коэффициенты a, b, c необходимо решить систему из трёх уравнений, а для этого необходимо знать координаты как минимум трёх точек, через которые проходит парабола ρ(x). В связи с этим, в отличие от предыдущих методов, для вычисления площади отдельной криволинейной трапеции понадобиться не две, а три точки.

Для вывода формулы Симпсона рассмотрим подробнее i -ю криволинейную трапецию ограниченную сверху параболой ρ_i(x). Для упрощения расчётов сделаем следующие преобразования. Перенесём i -ю криволинейную трапецию в начало координат так, что x_i= 0 (следовательно, x_i-h=-h, x_i+h=h). Очевидно, что её площадь не изменится. Найдём её площадь (Рис. 10). Для нахождения площади криволинейной трапеции необходимо знать форму кривой ограничивающей её. В нашем случае это парабола . Для нахождения коэффициентов a_i, b_i, c_i составим систему из трёх уравнений. Для простоты обозначим a_i≡a, b_i≡b, c_i≡c, f(x_i-h)≡f₀, f(x_i)≡f₁, f(x_i+h)≡f₁. Тогда

Таким образом, получаем

. (42)

. (43)

Таким образом, получаем общую формулу Симпсона:

Для упрощения этой формулы учтём, что , , , где a и b – границы отрезка интегрирования [a, b]. С учётом этого получим:

,

где n – количество отрезков длиною 2h. То есть количество отрезков h, на которые разбит отрезок [a, b] должно быть обязательно чётным. Длина отрезка [a, b] равна 2nh.

Для оценки погрешности формулы Симпсона на отрезке [x_i-h, x_i+h] разложим функцию f(x) по формуле Тейлора до пятого члена с центром разложения в точке x_i. То есть

(44)

Тогда с учётом (43) и (44) получим:

Т.е.

, (45)

Сравнив формулы (45), (36), (30) и (19) увидим, что метод Симпсона является наиболее точным из всех описанных методов численного интегрирования.

Учитывая, что для метода Симпсона , запишем формулы оценки n и h для заданного ε. Для непрерывной :

,

.

Мажорантные оценки для кусочно-непрерывной :

,

.

Построим блок-схему.

Приближение функций

Как известно, функцию можно задать многими способами. Самые распространённые из них – это аналитический, графический и табличный. В первых двух способах функция обычно определена на бесконечном числе точек, третий же способ задаёт лишь их конечное количество, например, экспериментальные данные или результаты сложных вычислений. В связи с этим встаёт вопрос получения промежуточных значений таблично заданной функции. Для их нахождения используют два способа: интерполяция (экстраполяция)* и аппроксимация.

При использовании интерполяции считают табличные значения точными и интерполяционный многочлен должен точно проходить через заданные точки (Рис. 11). Аппроксимирующая же функция лишь приближается как можно ближе к заданным точкам, но не обязательно через них проходит (Рис. 13). Это связано с тем, что табличные данные считаются приближенными, и точное прохождение функции через эти точки будет только увеличивать ошибку.

Интерполяция

Итак, как было сказано выше, задачей интерполяции является поиск такого многочлена, график которого проходит через заданные точки.

Пусть функция y=f(x) задана с помощью таблицы (табл. 1).

Таблица 1

x	x0	x1	x2	…	xn
y	y0	y1	y2	…	yn

Необходимо получить многочлен P_n(x) такой, чтобы выполнялось условие:

P_n(x_i)=y_i. (46)

Для этого зададимся конкретным видом многочлена. Пусть P_n(x) имеет следующий вид:

P_n(x_i)=a₀+a₁x+a₂x²+…+a_nxⁿ. (47)

Для того, чтобы определить коэффициенты a₀, a₁,… необходимо решить систему из n уравнений с n неизвестными:

(48)

Полином с коэффициентами, полученными путём решения системы (48) называют интерполяционным полиномом Лагранжа и обозначают L_n(x). Решение системы (48) весьма трудоёмко, поэтому интерполяционный полином Лагранжа представляют в виде линейной комбинации многочленов степени n:

. (49)

Необходимо, чтобы каждый многочлен l_i(x) обращался в нуль во всех узлах интерполяции, за исключением i -го, в котором он равен 1 (Рис. 12). Если l_i(x) удовлетворяет таким условиям, то в i -ом узле интерполяции многочлен L_n(x) примет значение y_i, что удовлетворяет условию поставленной задачи. Таким условиям удовлетворяет многочлен вида:

. (50)

Таким образом, интерполяционный многочлен Лагранжа можно представить следующей общей формулой:

(51)

С использованием формулы (51) построим блок-схему алгоритма метода интерполяции функции полиномом Лагранжа.

Аппроксимация

В задачу аппроксимации входит нахождение такой функции y=f(x), что расстояния между заданными точками y_i и значениями f(x_i) были минимальными (Рис. 13). Обозначим отклонение:

ε_i=y_i-f(x_i)

В качестве оценки общего отклонения кривой f(x) от табличных данных (Табл. 1) можно было бы взять сумму отклонений ε_i, но отклонения могут быть разными по знаку и, не смотря на большие ε_i их сумма может быть близка к нулю. Очевидно, что необходимо брать сумму абсолютных значений отклонений, но на практике неудобно пользоваться этой функцией, поэтому в качестве критерия оценки отклонения кривой берут сумму квадратов отклонений:

. (52)

Для определения функции f(x) необходимо, во-первых, задать её общий вид, например, f(x)=ax+b, во-вторых, подставив f(x) в (52) и минимизировав σ, найти коэффициенты (a и b). Такой метод определения коэффициентов для функции f(x) называется методом наименьших квадратов. Наиболее часто встречающиеся виды функции f(x) для метода наименьших квадратов приведены в таблице 2. Формула y=f(x) называется эмпирической формулой или уравнением регрессии y на x.

Таблица 2

Общий вид функции	Аналитическая формула	Вид регрессии
y=f(x,a,b)	y=ax+b	линейная
y=f(x,a,m)	y=axm	степенная
y=f(x,a,m)	y=aemx	показательная
y=f(x,a,b)		дробно-линейная
y=f(x,a,b)		логарифмическая
y=f(x,a,b)		гиперболическая
y=f(x,a,b)		дробно-рациональная

Рассмотрим подробнее метод наименьших квадратов на примере линейной регрессии, т.е. общий вид функции такой: f(x)=ax+b. Требуется найти методом наименьших квадратов коэффициенты a и b. Для определения минимального σ необходимо приравнять нулю частные производные этой функции по параметрам a и b. Для случая линейной регрессии формула (52) приводится к следующему виду:

. (53)

Условие экстремума запишется так:

. (54)

Отсюда получаем систему из двух уравнений с двумя неизвестными.

(55)

(56)

(57)

Итак, коэффициенты линейной регрессии вычисляются по формулам (57), но для определения параметров других видов регрессии выводить аналогичные формулы необязательно. Можно воспользоваться уже полученными. Для этого будем приводить все виды регрессии к линейному виду.