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

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

Содержание

Постановка задачи

Рассмотрим методы численного решения уравнений и систем уравнений:

f(x_1, x_2, \ldots, x_n)=0\!

или

\left\{ \begin{array}{lcr}
f_1(x_1, x_2, \ldots, x_n) & =& 0 \\
\ldots & & \\
f_n(x_1, x_2, \ldots, x_n) & =& 0
\end{array}\right.

Численное решение задачи можно проводить как непосредственно (используя одноимённые методы), так и с применением оптимизационных методов, приведя задачу к соответствующему виду. Последним посвящена статья Система уравнений и экстремальные задачи. Градиентные методы.

Численные методы решения уравнений

Покажем, как можно решить изначальную систему уравнений, не прибегая к оптимизационным методам. В случае, если наша система представляет собой СЛАУ, целесообразно прибегнуть к таким методам, как метод Гаусса, метод Крамера или метод Ричардсона. Однако мы всё же будем исходить из предположения, что вид функции нам неизвестен и воспользуемся одним из итерационных методов численного решения. Среди большого разнообразия таковых выберем один из наиболее известных — метод Ньютона. Этот метод в свою очередь основывается на принципах метода простой итерации. Поэтому сначала будет изложена суть последнего.

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

В основе метода заложено понятие сжимающего отображения. Определим терминологию:

Говорят, что функция \phi\! осуществляет сжимающее отображение на [a,\; b]\!, если

  1. \forall x \in [ a, \; b ]: \phi(x) \in [a,\; b ]\!
  2. \exist \alpha < 1: \forall x_1,x_2 \in [a,\; b ]\quad ||\phi(x_1)-\phi(x_2)||\leq \alpha ||x_1-x_2||\!

Тогда основная теорема будет выглядеть так:

Теорема Банаха (принцип сжимающих отображений).
Если \phi\! — сжимающее отображение на [a, \; b]\!, то:
  1. у x=\phi(x)\quad \exist ! x^*\in[a, \; b]\! — корень;
  2. итерационная последовательность x_{i+1}=\phi(x_i)\! сходится к этому корню;
  3. для очередного члена x_n\! справедливо ||x_n-x^*||\leq\frac{\alpha^n ||x_1-x_0||}{1-\alpha}\!.

Поясним смысл параметра \alpha\!. Согласно теореме Лагранжа имеем:

\phi(x) \in C^1[a, \; b].\quad \forall x_1,x_2 \in (a, \; b),\quad x_1<x_2 \quad \exist \xi \in (x_1,\; x_2): \quad \phi'(\xi)(x_2-x_1) = \phi(x_2)-\phi(x_1)\!

Отсюда следует, что \alpha \approx |\phi'(\xi)|\!. Таким образом, для сходимости метода достаточно, чтобы \forall x \in [a,\; b]\quad |\phi'(x)|\leq 1.\!

Применительно к СЛАУ

Рассмотрим систему:

\left\{ \begin{array}{ccc}
a_{11} x_1 + \ldots + a_{1n} x_n & = & b_1 \\
\ldots & & \\
a_{n1} x_1 + \ldots + a_{nn} x_n & = & b_n
\end{array}\right.

Для неё итерационное вычисление будет выглядеть так:

\left( \begin{array}{c}
x_1\\
x_2\\
\vdots\\
x_n \end{array}\right)^{i+1} = \left( \begin{array}{cccc}
a_{11}+1 & a_{12} & \ldots & a_{1n} \\
a_{21} & a_{22}+1 & \ldots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \ldots & a_{nn}+1
\end{array}\right) \left(\begin{array}{c}
x_1\\
x_2\\
\vdots\\
x_n
\end{array}\right)^{i}-\left(\begin{array}{c}
b_1\\
b_2\\
\vdots\\
b_n
\end{array}\right)

Сходимость методу будет осуществлять \left|\begin{array}{ccc}a_{11}+1 & \ldots & a_{n1} \\ \vdots & \ddots & \vdots\\ a_{n1} & \ldots & a_{nn}+1 \end{array} \right|<1

Алгоритм

  1. Условие f(x)=0\! преобразуется к виду x=\phi(x)\!, где \phi(x)\! — сжимающая
  2. Задаётся начальное приближение и точность x_0, \quad \varepsilon, \quad i=0\!
  3. Вычисляется очередная итерация x_{i+1}=\phi(x_i)\!
    • Если ||x_{i+1}-x_i||>\varepsilon\!, то i=i+1\! и возврат к шагу 3.
    • Иначе x=x_{i+1}\! и остановка.

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

Основная статья: Метод Ньютона

Одномерный случай

Для того, чтобы решить уравнение f(x)=0\!, пользуясь методом простой итерации, необходимо привести его к виду x=\phi(x)\!, где \phi\! — сжимающее отображение. Чтобы отображение было наиболее эффективно, необходимо, чтобы в точке очередной итерации x * выполнялось \phi'(x^*)=0\!. Будем искать решение данного уравнения в виде \phi(x)=x+\alpha(x) f(x)\!, тогда:

\phi'(x^*)=1+\alpha'(x^*) f(x^*) + \alpha(x^*) f'(x^*)=0\!

Воспользуемся тем, что f(x)=0\!, и получим окончательную формулу для \alpha(x)\!:

\alpha(x)=-\frac{1}{f'(x)}\!

С учётом этого сжимающая функция примет вид:

\phi(x)=x-\frac{f(x)}{f'(x)}\!

Тогда алгоритм нахождения численного решения уравнения f(x)=0\! сводится к итерационной процедуре вычисления:

x_{i+1}=x_{i}-\frac{f(x_i)}{f'(x_i)}\!

Многомерный случай

Обобщим полученный результат на многомерный случай.

Выбирая некоторое начальное приближение \vec{x}^{[0]}\!, находят последовательные приближения \vec{x}^{[j+1]}\! путем решения систем уравнений:

f_i + \sum_{k=1}^n\frac{\partial f_i}{\partial x_k}(x^{[j+1]}_k - x_k^{[j]})=0,\quad i = 1, 2, \ldots, n\!,

где x^{[j]}=\left( x_1^{[j]} \ldots x_k^{[j]} \ldots x_n^{[j]} \right), \quad j = 0, 1, 2, \ldots\!.

Литература

  1. Амосов А.А., Дубинский Ю. А., Копченова Н.П. Вычислительные методы для инженеров. — М.: Мир, 1998.
  2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.Г. Численные методы. — 8-е изд.. — М.: Лаборатория Базовых Знаний, 2000.
  3. Волков Е.А. Численные методы. — М.: Физматлит, 2003.
  4. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.

См. также


Wikimedia Foundation. 2010.

Смотреть что такое "Метод простой итерации" в других словарях:

  • ПРОСТОЙ ИТЕРАЦИИ МЕТОД — метод приближенного решения системы линейных алгебраич. уравнений Ах=b, к рая преобразуется к виду х=Вх+с и решение к рой находится как предел последовательности xk+1=Bxk+c, k=0, 1, . . ., где х 0 начальное приближение. Для сходимости П. и. м.… …   Математическая энциклопедия

  • Простой итерации метод — Стационарный итерационный метод это метод, который может быть представлен в следующей простой форме: xk = Bxk − 1 + c, где B и c не зависят от номера итерации k. Стационарные итерационные методы метод Якоби метод Гаусса Зейделя …   Википедия

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

  • Метод одной касательной — Метод Ньютона (также известный как метод касательных)  это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… …   Википедия

  • Метод Гаусса — Ньютона — Метод Ньютона (также известный как метод касательных)  это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… …   Википедия

  • Метод Ньютона-Рафсона — Метод Ньютона (также известный как метод касательных)  это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… …   Википедия

  • Метод Ньютона — Рафсона — Метод Ньютона (также известный как метод касательных)  это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… …   Википедия

  • Метод касательной — Метод Ньютона (также известный как метод касательных)  это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… …   Википедия

  • Метод касательной (Метод Ньютона) — Метод Ньютона (также известный как метод касательных)  это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… …   Википедия

  • Метод касательных — Метод Ньютона (также известный как метод касательных)  это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643 1727), под именем… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»