Второй этап. Этап уточнения корня

Iteration (итерация)- повторение, ре-зультат повторного применения какой-либо математической операции.

Этап уточнения корня заключается в построении последовательности приближенных значений ( итераций ) корня уравнения (2.1), исходя из начального приближения корня x₀ (нулевой итерации).

Эта последовательность

x₀, x₁, x₂, ……x_n …. (2.4)

называется итерационной последовательностью.

Если существует предел этой последовательности, т.е.

, (2.5)

то говорят, что итерационный процесс (2.4) сходится и сходится к точному решению уравнения x ^*[2].

На практике итерационный процесс ограничивают конечным числом шагов (итераций) n. Количество итераций зависит от требуемой точности нахождения корня.

Для прекращения итерационного процесса применяются различные критерии, зависящие от вида функции y=f(x) в окрестности корня.

1. Если функция достаточно «пологая», то итерационный процесс продолжается до тех пор, пока две соседние итерации не станут достаточно близкими, т.е. пока не выполнится условие:

(2.6)

2. Если функция у=f(x) «круто» меняет свои значения, целесообразно использовать условие:

(2.7)

Если условие (2.6) или (2.7) выполняется, то в качестве приближенного решения уравнения (2.1) с заданной точностью e принимают n-ю итерацию т.е.

Если ни одно из этих условий не выполняется, то итерационный процесс необходимо продолжить.

Рассмотрим несколько итерационных (приближенных) методов решения нелинейных уравнений. Выбор того или иного метода зависит от вида функции y = f(x).

Метод половинного деления (бисекции)

Пусть функция y=f(x) удовлетворяет условиям теоремы 2.1 на отрезке [a, b], т.е. уравнение (2.1) имеет единственный корень на этом отрезке.

Метод половинного деления (бисекции) это один из простейших методов решения нелинейных уравнений. Приводим алгоритм и геометрическую интерпретацию (рис.2.5) этого метода.

Алгоритм метода бисекции.

1. Делим отрезок [a, b] пополам.

2. Если , то является корнем уравнения (2.1).

3. Если , то из двух отрезков выбираем тот, на концах которого функция f(x) имеет разные знаки.

Рис. 2.5. Схема метода бисекции

4. Новый «суженный» отрезок [a₁, b₁] снова делим пополам и проводим тот же анализ и т.д.

5. В результате получаем на каком-то этапе или точный корень уравнения (2.1), или же бесконечную последовательность вложенных друг в друга отрезков,

[a₁, b₁], [a₂, b₂], …………………[a_n, b_n]

таких, что f(a_i, ) f(b_i)< 0, (i=1, 2, …..) (2.8)

и (2.9)

Левые концы a₁, a₂, ..., a_n, … и правые концы b₁, b₂, ..., b_n, … этих отрезков образуют монотонные последовательности, соответственно неубывающую и невозрастающую.

Доказывается утверждение, что существует общий пре-дел x*, который является корнем уравнения (2.1).

(2.10)

Метод половинного деления легко реализуется на ЭВМ по следующей схеме.

Для нахождения приближенного значения корня уравнения (2.1) с заданной точностью e необходимо циклически повторить следующую последовательность действий:

1. отрезок [a, b] делим пополам ,

2. если │ f(x)│ > ε, переходим на пункт 3, иначе – на пункт 5,

3. если f(x)*f(b) ≤ 0, то принимаем a = x, иначе b = х. Т.е. из двух отрезков выбираем тот, на концах которого функция имеет разные знаки, и новый «суженный» отрезок вновь называем отрезком [a, b],

4. если │ a-b│ > ε, то выполняется пункт 1, иначе – пункт 5.

5. в качестве приближенного решения уравнения (2.1) с заданной точностью ε принимается .

G Замечание. Метод половинного деления практически удобно применять для грубого нахождения корня заданного уравнения, поскольку при увеличении точности объем вычислительной работы значительно возрастает.

Метод хорд

Пусть функция y=f(x) на отрезке [a, b] удовлетворяет условиям теорем 2.1, т.е. уравнение f(x)=0 имеет на этом отрезке единственный корень x^*.

Положим для определенности f ^’’(x)> 0 (рис.2.6). Вместо деления отрезка пополам, разделим его в отношении f(a): f(b).

С геометрической точки зрения способ пропорциональных частей эквивалентен замене кривой y=f(x) хордой, проходящей через точки A[a, f(a)] и B[b, f(b)].

Для построения итерационной последовательности по методу хорд необходимо выбрать начальное приближение (нулевую итерацию) х_0.

Если функция y=f(x) имеет 2-ую производную, сохраняющую знак на этом отрезке, то начальное приближение х₀выбирается, исходя из условия:

f(x₀) f ”(x₀ ) < 0. (2.11)

Рассмотрим два случая, каждый из которых определен видом функции y = f(x) на отрезке [a, b].

Первый случай. Полагаем f(а)> 0, f(b)< 0 и f ^’’(x)> 0 для xÎ [a, b] (рис.2.6).

1. В качестве нулевого приближения корня выбирается тот конец отрезка [a, b], для которого выполняется условие (2.11), т.е выбираемправый конец отрезка [a, b], х₀=b.

2. Проводим хорду АВ₀ и за первое приближение (первую итерацию) х₁ принимаем абсциссу точки пересечения хорды с осью ОХ.

3. Второе приближение х₂получаем как абсциссу точки пересечения хорды АВ₁ с осью ОХ.

4. Аналогичным образом строим итерационную последовательность:

х₀=b, x₁, x₂, ……., x_n, ….

В математическом анализе доказывается теорема, что эта итерационная последовательность сходится к корню уравнения х^* (2.1).

Для получения формулы (n+1)-ой итерации х_n₊₁ запишем уравнение хорды AB_n:

Полагая х=x_n₊₁и y = 0 найдем абсциссу точки пересечения хорды AB_n с осью ОХ, т.е. (n+1)-ю итерацию х_n₊₁.

Рис.2.6. Схема метода хорд (1-й случай)

В этом случае левый конец отрезка [a, b] неподвижен и последовательные приближения (итерации) определяются по формуле:

(2.13)

Второй случай. Полагаем f(а)< 0, f(b)> 0 и f ^’’ (x)> 0 для xÎ [a, b] (рис.2.7).

В качестве нулевого приближения корня выбираем тот конец отрезка [a, b], для которого справедливо условие (2.11).

Для данного случаявыбирается левый конец отрезка [a, b], т.е. х₀=а, а в качестве неподвижного конца: х=b.

Аналогично первому случаю строим последовательность приближений, сходящуюся к точному решению х^*уравнения (2.1) и определяемую следующим соотношением:

(2.14)

Рис.2.7. Схема метода хорд (2-й случай)

Таким же образом рассматриваются еще два случая, когда вторая производная отрицательна, т.е. f ^’’ (x)< 0 на отрезке [a, b].

Следующая теорема обобщает все четыре случая для приближенного решения нелинейного уравнения (2.1) по методу хорд.

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒