Решение уравнений методом итерации

Размещено на http://allbest.ru

Решение уравнений методом итерации

Исследовать метод простой итерации для решения систем линейных алгебраических уравнений, а именно: влияние способа перехода от системы F(x)=x к системе x=(x) на точность полученного решения, скорость сходимости метода, время счета, число операций.

Пусть дана система линейных алгебраических уравнений в виде Ax=b (2.2.1).

Пусть (2.2.1.) приведена каким-либо образом к виду x=Cx+f (2.2.2), где C - некоторая матрица, f - вектор-столбец. Исходя из произвольного вектора

строим итерационный процесс x^{( k+1 )}=Cx^{( k )}+f (k=0,1,2,3,…) или в развернутой форме

Производя итерации, получим последовательность векторов x^{( 1 )}, x^{( 2)},…, x^{( k )},… Доказано, что если элементы матрицы C удовлетворяют одному из условий

то процесс итерации сходится к точному решению системы x при любом начальном векторе x⁽⁰⁾, то есть

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

если выполнено условие (2.2.4), или

алгебраический итерация уравнение матрица

если выполнено условие (2.2.5). Эти оценки можно еще усилить соответственно так:

Процесс итераций заканчивают, когда указанные оценки свидетельствуют о достижении заданной точности.

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

Приведение системы (2.2.1) к виду (2.2.2) можно осуществить различными способами. Важно только, чтобы выполнялось одно из условий (2.2.4) или (2.2.5). Ограничимся рассмотрением двух таких способов.

Первый способ. Если диагональные элементы матрицы А отличны от нуля, то есть a_ii0 ( i=1,2,…,n), то систему (2.2.1) можно записать в виде

В этом случае элементы матрицы С определяются следующим образом:

и тогда условия (2.2.4) и (2.2.5) соответственно приобретают вид

Неравенства (2.2.7), (2.2.8) будут выполнены, если диагональные элементы матрицы А удовлетворяют условию

то есть если модули диагональных коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов (не считая свободных членов).

Второй способ позволяет записать систему (2.2.1) в виде

Это способ численного решения математических задач. Его суть - нахождение алгоритма поиска по известному приближению (приближенному значению) искомой величины следующего, более точного приближения.

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

Данный метод называют также методом последовательных приближений, методом повторных подстановок, методом простых итераций и т.п.

Поясним суть метода на примере решения уравнения

f(x) = 0. (1)

Будем вместо уравнения (1) рассматривать равносильное ему уравнение

х = F(x), (2)

где F(x) = f(x) + х.

Пусть х₀ - произвольное число (начальное приближение искомого корня уравнения (1)).

Рассмотрим последовательность

х₁ = F(x₀), x₂ = F(x₁), …, x_n= F(x_n-1), …

Если эта последовательность имеет предел, то он и есть решение (корень) уравнения (2), а значит, и уравнения (1).

Процесс составления последовательных приближений наглядно показан на рис., где кривая - график функции у = F(x), а прямая - биссектриса первого и третьего координатных углов (ее уравнение у = х).

Последовательность {x_n} сходится, например, если выполнены оба условия:

,

где е > 0 - достаточно малое положительное число (в этом случае как раз и будет ситуация, изображенная на рисунке). Заметим, что функцию F(x) в уравнении (2) можно выбирать разными способами (не только как f(x) + x).

Например, уравнение х² - 5 = 0 можно переписать в таких равносильных (ему и друг другу) формах:

.

Понятно, что этот список можно неограниченно продолжить.

Выбрав некоторую функцию F(x), дальше продолжают описанную процедуру последовательных приближений.

Если функция F(x) непрерывна в некоторой окрестности искомого корня, то в силу соответствующих свойств пределов непрерывных функций из равенства х_n= F(x_n-1) следует, что

,

т.е. в пределе выполняется равенство (2), а значит и (1).

Из свойств пределов вытекает также, что для достаточно больших значений n разность между x_n и предельным значением x_n (т.е. искомым корнем уравнения (1)) становится как угодно малой, т.е. x_n - достаточно хорошее приближение для искомого корня.

В качестве примера укажем способ вычисления квадратного корня из положительного числа а - положительного корня уравнения х² - а = 0, равносильного уравнению

.

Выбирается «нулевое» положительное приближение корня и строится последовательность приближений, пока модуль разности х_n - x_n-1 не станет меньше заданной точности вычислений.

Пример: Найдем значение с точностью до 0,001.

Поскольку 2 < < 3, примем х₀ = 2. Тогда:

Мы видим, что требуемая точность приближения достигнута уже на третьем приближении х₃.

Ответ: с точностью до 0,001 выполнено равенство =2,6457.

Для вычисления корня k-й степени из числа а уравнение х^k = a часто записывают в виде

,

выбирают нулевое приближение, а дальше применяют метод последовательных приближений.

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

Если функция у = F(x) монотонна на отрезке [a; b], причем отрезок с концами F(a) и F(b) лежит на отрезке [a; b] и существует такое число q, что

0 < q < 1 и |F`(x)| < q,

то на этом отрезке лежит единственный корень уравнения х = F(x), и процесс приближения, начинающийся с любого числа , сходится к этому корню(*).

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

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

Размещено на Allbest.ru