Метод простых итераций Приближённое нахождение корней уравнений


Предположим, что уравнение $ f(x)=0$ при помощи некоторых тождественных преобразований приведено к виду $ x={\varphi}(x)$.

Заметим, что такое преобразование можно вести разными способами, и при этом будут получаться разные функции $ {\varphi}(x)$ в правой части уравнения. Уравнение $ f(x)=0$ эквивалентно уравнению $ x=x+{\lambda}(x)f(x)$ при любой функции $ {\lambda}(x)\ne0$. Таким образом, можно взять $ {\varphi}(x)=x+{\lambda}(x)f(x)$ и при этом выбрать функцию (или постоянную) $ {\lambda}\ne0$ так, чтобы функция $ {\varphi}(x)$ удовлетворяла тем свойствам, которые понадобятся нам для обеспечения нахождения корня уравнения.

Для нахождения корня уравнения $ x={\varphi}(x)$ выберем какое-либо начальное приближение $ x_0$ (расположенное, по возможности, близко к корню $ x^*$). Далее будем вычислять последующие приближения

$\displaystyle x_1,x_2,\dots,x_i,x_{i+1},\dots$ Числовые ряды Математика решение задач

по формулам

$\displaystyle x_1={\varphi}(x_0);x_2={\varphi}(x_1);\dots;x_{i+1}={\varphi}(x_i);\dots\quad,$

то есть используя каждое вычисленное приближение к корню в качестве аргумента функции $ {\varphi}(x)$ в очередном вычислении. Такие вычисления по одной и той же формуле $ x_{i+1}={\varphi}(x_i)$, когда полученное на предыдущем шаге значение используется на последующем шаге, называются итерациями. Итерациями называют часто и сами значения $ x_i$, полученные в этом процессе (то есть, в нашем случае, последовательные приближения к корню).

Заметим: тот факт, что $ x^*$ -- корень уравнения $ x={\varphi}(x)$, означает, что $ x^*$ есть абсцисса точки пересечения графика $ y={\varphi}(x)$ с прямой $ y=x$. Если же при каком-либо $ x_0$ вычислено значение $ x_1={\varphi}(x)$ и взято в качестве нового аргумента функции, то это означает, что через точку графика $ (x_0;{\varphi}(x_0))$ проводится горизонталь до прямой $ y=x$, а оттуда опускается перпендикуляр на ось $ Ox$. Там и будет находиться новый аргумент $ x_1$.

Рис.9.3.Точка $ x^*$ -- решение уравнения $ x={\varphi}(x)$. Построение точки $ x_1$ по точке $ x_0$

Проследим, как изменяются последовательные приближения $ x_i$ при различных вариантах взаимного расположения графика $ y={\varphi}(x)$ и прямой $ y=x$.

1). График $ y={\varphi}(x)$ расположен, по крайней мере в некоторой окрестности корня, включающей начальное приближение $ x_0$, в некотором угле со сторонами, имеющими наклон менее $ \frac{\pi}{4}$ к горизонтали (то есть стороны угла -- прямые $ y=f(x^*)\pm k(x-x^*)$, где $ 0<k<1$):

 

Рис.9.4.График пересекает прямую $ y=x$ под малым углом: варианты расположения

Если предположить вдобавок, что функция $ {\varphi}(x)$ имеет производную $ {\varphi}'(x)$, то этот случай соответствует тому, что выполнено неравенство $ \vert{\varphi}'(x)\vert<1$, при $ x$, близких к корню $ x^*$. Проследим в этом случае за поведением последовательных приближений $ x_0,x_1,\dots.$

Рис.9.5.Сходящиеся к корню приближения в случае $ \vert{\varphi}(x)\vert<1$: два варианта

Мы видим, что каждое следующее приближение $ x_{i+1}$ будет в этом случае расположено ближе к корню $ x^*$, чем предыдущее приближение $ x_i$. При этом, если график при $ x<x^*$ лежит ниже горизонтали $ y={\varphi}(x^*)$, а при $ x>x^*$ -- выше её (что, в случае наличия производной, верно, если $ 0<{\varphi}'(x)<1$), то приближения $ x_i$ ведут себя монотонно: если $ x_0<x^*$, то последовательность $ \{x_i\}$ монотонно возрастает и стремится к $ x^*$, а если $ x_0>x^*$, то монотонно убывает и также стремится к $ x^*$. Если же график функции $ {\varphi}(x)$ лежит выше горизонтали $ y={\varphi}(x^*)$ при $ x<x^*$ и ниже её при $ x>x^*$ (это так, если $ -1<{\varphi}'(x)<0$), то последовательные приближения $ x_i$ ведут себя иначе: они "скачут" вокруг корня $ x^*$, с каждым скачком приближаясь к нему, но так же стремятся к $ x^*$ при $ i\to\infty$.

Заметим, что если функция $ {\varphi}(x)$ не монотонна в окрестности точки $ x^*$, то последовательные приближения могут вести себя нерегулярно (то есть не монотонно и не оказываясь попеременно то левее, то правее корня, а делая скачки относительно корня при произвольных номерах (см. следующий чертёж):

Рис.9.6.В случае немонотонной функции $ {\varphi}$ сходящиеся итерации могут вести себя нерегулярно

 

Основные обозначения и определения Функции и их графики

 

Пример 1.4 При сдаче пальто в гардероб каждому сданному пальто $ p$ соответствует ровно один выданный номерок $ n$. Таким образом, между множеством $ P$ сданных пальто и множеством выданных номерков $ N'$ ($ N'$-- это подмножество множества $ N$ всех номерков в гардеробе) устанавливается биекция $ f: p\mapsto n$ ($ p\in P$, $ n\in N'$).

Определение 1.4 Если $ f:A\to B$-- биекция, то отображение, сопоставляющее каждому $ y\in B$ тот элемент $ x\in A$, который переходит в этот самый $ y$ при отображении $ f$, называется обратным отображением (или обратной функцией) к отображению $ f$ и обозначается $ f^{-1}$. Таким образом, $ f^{-1}:B\to A$, и $ f^{-1}(y)=x$ тогда и только тогда, когда $ f(x)=y$ ($ x\in A$, $ y\in B$).

Пример 1.5 В условиях примера 1.4 отображение $ f:P\to N'$-- биекция. При выдаче пальто из гардероба по каждому из выданных номерков $ n\in N'$ находят соответствующее номерку пальто $ p\in P$. Соответствие $ g:N'\to P$, $ n\mapsto p$ ($ n\in N'$, $ p\in P$)-- это обратная функция к функции $ f:P\to N'$, $ p\mapsto n$, то есть $ g=f^{-1}$.

Классификация операционных систем Виртуальная память Реализация многозадачности
Системы безопасности Операционная система Linux Введение в компьютерные сети Принципы построения вычислительных систем Базовые технологии локальной сетиСредства анализа Процедуры и функции Pascal Язык запросов SQL Программирование на СИ Брандмауэры Протоколы TCP/IP Файловые системы Драйверы устройств