Курсовая работа: Приближённые методы решения алгебраического уравнения

Приступим к доказательству того, что если непрерывная функция принимает на концах некоторого отрезка [a, b] значения разных знаков, то методом дихотомии однозначно будет найден корень.

Предположим для определённости, что функция f(x) принимает на левом конце отрезка [a, b] отрицательное значение, а на правом – положительное:

f(a) < 0, f(b) > 0.

Возьмём среднюю точку отрезка [a, b], h=(a+b)/2 и вычислим значение в ней функции f(x). Если f(h)=0, то утверждение теоремы доказано: мы нашли такую точку, где функция обращается в нуль. Если f(h)¹ 0, тогда из отрезков [a, h] и [h, b] выберем один из них тот, где функция на его концах принимает значения разных знаков. Обозначим его [a₁ , b₁ ]. По построению: f(a₁ )<0, f(b₁ )>0. Затем среднюю точку отрезка [a₁ , b₁ ] точку h₁ и проведём тот же алгоритм нахождения другого отрезка [a₂ , b₂ ] где бы по построению f(a₂ )<0, f(b₂ )>0. Будем продолжать этот процесс. В результате он либо оборвётся на некотором шаге n в силу того, что f(h_n )=0, либо будет продолжаться неограниченно. В первом случае вопрос о существовании корня уравнения f(x)=0 решён, поэтому рассмотрим второй случай.

Неограниченное продолжение процесса даёт последовательность отрезков [a, b], [a₁ , b₁ ], [a₂ , b₂ ],… Эти отрезки вложены друг в друга – каждый последующий отрезок принадлежит всем предыдущим:

a_n £ a_{n+ 1} < b_{n+ 1} £ b_n (1.2)

причём:

f(a_n ) < 0, f(b_n ) > 0

Длины отрезков с возрастанием номера n стремятся к нулю:

Рассмотрим левые концы отрезков. Согласно (1.2) они образуют монотонно убывающую ограниченную последовательность {a_n }. Такая последовательность имеет предел, который можно обозначить через c₁ :

Согласно (1.1) и теореме о переходе к пределу в неравенствах имеем:

c₁ £ b_n (2.2)

Теперь рассмотрим правые концы отрезков. Они образуют монотонно не возрастающую ограниченную последовательность {b_n }, которая тоже имеет предел. Обозначим его через с₂ : . Согласно неравенству (2.1) пределы с₁ и с₂ удовлетворяют неравенству с₁ £ с₂ . Итак, a_n £ с₁ < с₂ £ b_n , и следовательно:

с₂ -с₁ £ b_n - a_n =(b-a)/2n.

Таким образом, разность с₂ -с₁ меньше любого наперёд заданного положительного числа. Это означает, что с₂ -с₁ =0, т. е.: с₁ =с₂ =с

Найденная точка интересна тем, что она является единственной общей точкой для всех отрезков построенной последовательности Используя непрерывность функции f(x), докажем, что она является корнем уравнения f(x)=0.

Мы знаем, что f(a_n )<0. Согласно определению непрерывности и возможности предельного перехода в неравенствах, имеем:

f(c)=lim f(a_n )£0 (3.2)

Аналогично, учитывая, что f(b_n )³0, получаем, что:

f(c)=lim f(b_n ) ³0 (4.2)

Из (3.2) и (4.2) следует, что f(c)=0. т. е. с – корень уравнения.

Процесс построения последовательности вложенных стягивающих отрезков методом вилки (дихотомии) является эффективным вычислительным алгоритмом решения уравнения f(x)=0. На n-ом шаге процесса получаем:

a_n £ c £ b_n

Это двойное неравенство показывает, что число a_n определяет корень с недостатком, а число b_n с избытком, с ошибкой не превышающей длину отрезка Dn=b_n -a_n =(b-a)/2n. При увеличении n ошибка стремится к нулю по закону геометрической прогрессии со знаменателем q=0.5. Если задана требуемая точность e>0, то чтобы её достигнуть достаточно сделать число шагов N, не превышающее log₂ [(b-a)/e]: N>log₂ [(b-a)/e].

3. Метод итераций

Этот метод называется ещё методом последовательных приближений.

Пусть нам необходимо найти корень уравнения (1.1) на некотором отрезке [a, b].

Предположим, что уравнение (1.0) можно переписать в виде:

x=j(x) (1.3)