Теоретическая часть
Метод простой итерации
Рассмотрим уравнение
f(x)=0 |
с отделенным корнем X [a, b]. Для решения уравнения методом простой итерации приведем его к равносильному виду:
x=φ(x) |
Это всегда можно сделать, причем многими способами. Например: x=g(x) · f(x) + x ≡ φ(x), где g(x) - произвольная непрерывная функция, не имеющая корней на отрезке [a,b].
Пусть x(0) - полученное каким-либо способом приближение к корню x (в простейшем случае x(0)=(a+b)/2). Метод простой итерации заключается в последовательном вычислении членов итерационной последовательности:
x(k+1)=φ(x(k)), k=0, 1, 2,... |
начиная с приближения x(0).
Утверждение: Если последовательность {x(k)} метода простой итерации сходится и функция φ непрерывна, то предел последовательности является корнем уравнения x=φ(x)
Доказательство: Пусть
Перейдем к пределу в равенстве x(k+1)=φ(x(k)) Получим с одной сторонv по, что а с другой стороны в силу непрерывности функции φ.
В результате получаем x*=φ(x*). Следовательно, x* - корень уравнения, т.е. X=x*.
Чтобы пользоваться этим утверждением нужна сходимость последовательности {x(k)}. Достаточное условие сходимости дает:
Теорема (о сходимости) Пусть уравнение x=φ(x) имеет единственный корень на отрезке [a,b] и выполнены условия:
1) φ(x) C1[a,b];
2) φ(x) [a,b] x [a,b];
3) существует константа q > 0: | φ '(x) | ≤ q < 1 x [a,b]. Tогда итерационная последовательность {x(k)}, заданная формулой x(k+1) = φ(x(k)), k=0, 1,... сходится при любом начальном приближении x(0) [a,b].
Доказательство Рассмотрим два соседних члена последовательности {x(k)}: x(k) = φ(x(k-1)) и x(k+1) = φ(x(k)) Tак как по условию 2) x(k) и x(k+1) лежат внутри отрезка [a,b], то используя теорему Лагранжа о средних значениях получаем:
x (k+1) - x (k) = φ(x (k)) - φ(x (k-1)) = φ '(c k)(x (k) - x (k-1))
где c k (x (k-1), x (k)).
Отсюда получаем:
| x (k+1) - x (k) | = | φ '(c k) | · | x (k) - x (k-1) | ≤ q | x (k) - x (k-1)| ≤ ≤ q (q | x (k-1) - x (k-2) |) = q 2 | x (k-1) - x (k-2) | ≤... ≤ q k | x (1) - x (0) | |
Рассмотрим ряд
S∞ = x (0) + (x (1) - x (0)) +... + (x (k+1) - x (k)) +.... |
Если мы докажем, что этот ряд сходится, то значит сходится и последовательность его частичных сумм
Sk = x (0) + (x (1) - x (0)) +... + (x (k) - x (k-1)).
Но нетрудно вычислить, что
Sk = x (k) |
Следовательно, мы тем самым докажем и сходимость итерационной последовательности {x(k)}.
Для доказательства сходимости pяда сравним его почленно (без первого слагаемого x(0)) с рядом
q 0 | x (1) - x (0) | + q 1 |x (1) - x (0)| +... + |x (1) - x (0)| +..., |
который сходится как бесконечно убывающая геометрическая прогрессия (так как по условию q < 1). В силу неравенства абсолютные величины ряда не превосходят соответствующих членов сходящегося ряда (то есть ряд мажорирует ряд). Следовательно ряд также сходится. Tем самым сходится последовательность {x(0)}
Получим формулу, дающую способ оценки погрешности |X - x (k+1)| метода простой итерации.
Имеем X - x(k+1) = X - Sk+1 = S∞ - Sk+1 = (x(k+2) - (k+1)) + (x(k+3) - x(k+2)) +.... Следовательно |X - x(k+1)| ≤ |x(k+2) - (k+1) | + |x(k+3) - x(k+2) | +... ≤ qk+1 |x(1) - x(0) | + qk+2 |x(1) - x(0) | +... = qk+1|x(1) - x(0) | / (1-q)
В результате получаем формулу
|X - x(k+1)| ≤ qk+1|x(1) - x(0) | / (1-q) |
Взяв за x(0) значение x(k), за x(1) - значение x(k+1) (так как при выполнении условий теоремы такой выбор возможен) и учитывая, что при имеет место неравенство qk+1 ≤ q выводим:
|X - x(k+1)| ≤ qk+1|x(k+1) - x(k) | / (1-q) ≤ q|x(k+1) - x(k) | / (1-q)
Итак, окончательно получаем:
|X - x(k+1)| ≤ q|x(k+1) - x(k) | / (1-q) |
Используем эту формулу для вывода критерия окончания итерационной последовательности. Пусть уравнение x=φ(x) решается методом простой итерации, причем ответ должен быть найден с точностью ε, то есть |X - x(k+1)| ≤ ε. С учетом получаем, что точность ε будет достигнута, если выполнено неравенство
|x(k+1)-x(k)| ≤ (1-q)/q |
Tаким образом для нахождения корней уравнения x=φ(x) методом простой итерации с точностью нужно продолжать итерации до тех пор, пока модуль разности между последними соседними приближениями остается больше числа ε(1-q)/q.
Замечание: В качестве константы q обычно берут оценку сверху для величины
Пример: Составим последовательность для решения уравнения f(x)=x·ex=0 по методу простой итерации.
Приведем уравнение к итерационному виду:
x = e - x ≡ φ(x).
Далее графически произведем отделение корня.
Несложный анализ графика показывает, что корень X [e-1,1]. Tак как при x [e-1,1] и e-x [e-1,1], x [e-1,1], то в соответствии с теоремой итерационная последовательность x(k+1) = e - x(k), k=0, 1, 2,... гарантированно сходится к корню уравнения. В качестве начального приближения к корню можно взять x(0)=0.5(1+e-1).
Блок схема
Рис.1
Проверка метода простой итерации в MathCad
Для использования метода итерации исходное нелинейное уравнение f(х) = 0 заменяется равносильным уравнением
x = j(x). |
Пусть известно начальное приближение корня х = х0. Подставляя это значение в правую часть уравнения, получим новое приближение:
х1 = j(х0). |
Далее, подставляя каждый раз новое значение корня в, получаем последовательность значений:
Геометрически метод итерации может быть пояснен следующим образом. Построим на плоскости хОу графики функций у = х и у = j (х). Каждый действительный корень уравнения является абсциссой точки пересечения М кривой у = j (х) с прямой у = х (Рис.2, а).
Рис.2
Отправляясь от некоторой точки А0 [x0, j (x0)], строим ломаную А0В1А1В2А2… (“лестница”), звенья которой попеременно параллельны оси Ох и оси Оу, вершины А0, А1, А2, …лежат на кривой у=j (х), а вершины В1, В2, В3, …, - на прямой у = х. Общие абсциссы точек А1 и В1, А2 и В2, …, очевидно, представляют собой соответственно последовательные приближения х1, х2, … корня .
Возможен также другой вид ломаной А0В1А1В2А2 … – “спираль” (Рис.2, б). Решение в виде “лестницы” получается, если производная j' (х) положительна, а решение в виде “спирали”, если j' (х) отрицательна.
На Рисунке 6, а, б кривая у = j (х) в окрестности корня - пологая, то есть <1, и процесс итерации сходится. Однако, если рассмотреть случай, где >1, то процесс итерации может быть расходящимся (Рис.3).
Рис.3
Поэтому для практического применения метода итерации нужно выяснить достаточные условия сходимости итерационного процесса.
Теорема: Пусть функция j (х) определена и дифференцируема на отрезке [a, b], причем все ее значения j (х) [a, b].
Тогда, если существует правильная дробь q такая, что
q < 1
при a < x < b, то: 1) процесс итерации
сходится независимо от начального значения х0 I [a, b];
2) предельное значение является единственным корнем уравнения х = j (х) на отрезке [a, b].
Пример. Уравнение
f(x) = x3 – x – 1 = 0 |
имеет корень x [1, 2], так как f(1) = - 1 < 0 и f(2) = 5 > 0.
Уравнение можно записать в виде
х = х3 – 1. |
Здесь
j (х) = х3 – 1 и j' (х) = 3х2;
поэтому
j' (х) 3 при 1 х 2
и, следовательно, условия сходимости процесса итерации не выполнены.
Если записать уравнение в виде
то будем иметь:
.
Отсюда при 1 х 2 и значит, процесс итерации для уравнения быстро сойдется.
Найдем корень x уравнения с точностью до 10-2. Вычисляем последовательные приближения хn с одним запасным знаком по формуле
С точностью до 10-2 можно положить x = 1,324.
Создание программы
Для начала мы создаем Form1 с использованием TextBox и Label. TextBox используется для ввода данных: начала промежутка, конца промежутка и погрешность. А также для решение уравнения. Label используется для обозначения различных данных.
Form1.
Также мы создаем меню. При помощи Menu Editor Мы создаем четыре основных пункта: Файл, Решение, График, Справка. Файл будет открывать два подпункта: Сохранить, который будет сохранить изменения программы на диске, и Выход, который будет выходить из Form1. Решение будет выводит на последний TextBox решение уравнение по заданным данным. График будет переводить на Form2. Справка будет выводит подпункт О программе…,в которой будет говорится о созданной программе.