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

| Категория реферата: Рефераты по математике
| Теги реферата: сочинение по картине, курсовики скачать бесплатно
| Добавил(а) на сайт: Feona.

Если требуется найти корень с точностью Е, то про- должаем деление пополам до тех пор, пока длина отрезка не станет меньше 2Е. Тогда середина последнего отрезка даст значение корня с требуемой точностью.

Дихотомия проста и очень надёжна. К простому корню она сходится для любых непрерывных функций в том числе и не дифференцируемых; при этом она устой- чива к ошибкам округления. Скорость сходимости не ве- лика; за одну итерацию точность увеличивается пример- но вдвое, т. е. уточнение трёх цифр требует 10 итераций.
Зато точность ответа гарантируется. рис. 1.2

Приступим к доказательству того, что если непрерывная функция принимает на концах некоторого отрезка [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] выберем один из них тот, где функция на его концах принимает значения разных знаков. Обозначим его [a1, b1]. По построению: f(a1)0. Затем среднюю точку отрезка [a1, b1] точку h1 и проведём тот же алгоритм нахождения другого отрезка [a2, b2] где бы по построению f(a2)0. Будем продолжать этот процесс. В результате он либо оборвётся на некотором шаге n в силу того, что f(hn)=0, либо будет продолжаться неограниченно. В первом случае вопрос о существовании корня уравнения f(x)=0 решён, поэтому рассмотрим второй случай.

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

an ( an+ 1
< bn+ 1 ( bn (1.2) причём:

f(an) < 0, f(bn) > 0

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

[pic]

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

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

c1 ( bn
(2.2)

Теперь рассмотрим правые концы отрезков. Они образуют монотонно не возрастающую ограниченную последовательность {bn}, которая тоже имеет предел. Обозначим его через с2: [pic]. Согласно неравенству (2.1) пределы с1 и с2 удовлетворяют неравенству с1 ( с2. Итак, an ( с1 < с2 ( bn, и следовательно:

с2-с1 ( bn - an=(b-a)/2n.

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

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

Мы знаем, что f(an)0, то чтобы её достигнуть достаточно сделать число шагов N, не превышающее log2[(b-a)/(]: N>log2[(b-a)/(].

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

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

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

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

x=((x)
(1.3)

Возьмём произвольное значение x0 из области определения функции
((x) и будет строить последовательность чисел {xn}, определённых с помощью рекуррентной формулы: