Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



(метод последовательных приближений)

Предположим, что уравнение можно записать в виде

x=φ(x).

Возьмем произвольное значение xo из области определения функции φ(x) и будем строить последовательность чисел {xn}, определенных с помощью рекуррентной формулы:

xn+1 = φ(xn), n= 0, 1, 2, 3,...

Последовательность {xn} называется итерационной. При ее изучении встают два вопроса:

1. Можно ли процесс вычисления чисел xn продолжать неограниченно, т.е. будут ли числа xn принадлежать области определения функции φ(x)?

2. Если итерационный процесс бесконечен, то как ведут себя числа xn при n→ ∞?

При определенных ограничениях на функцию φ(x ) итерационная последовательность является бесконечной и сходится к корню уравнения:

xn =c, c= φ(c).

Функция φ(x) удовлетворяет на отрезке [a, b] условию Липшица, если существует такая постоянная α, что для любых x1 и x2, принадлежащих отрезку [a, b], имеет место неравенство

| φ(x1)- φ(x2)| ≤ α | x1 – x1 |.

Величину α в этом случае называют постоянной Липшица.

Если функция φ(x) удовлетворяет на отрезке [a, b]условию Липшица, то она непрерывна на этом отрезке.

Пусть xo - произвольная точка отрезка. Рассмотрим приращение функции φ(x) в этой точке

Δf =f(xo+ Δx) – f(xo).

Оценим его с помощью неравенства

| Δf| | ≤ α |Δ x|.

Таким образом, lim Δf =0, что означает непрерывность функции.

Условие Липшица имеет простой геометрический смысл. Возьмем на графике функции y= f(x) две произвольные точки: М1 с координатами (x1, f(x1)) и М2 с координатами (x2, f(x2)) (рис.3). Напишем уравнение прямой линии, проходящей через эти точки. Оно имеет вид

y=f(x1)+k(x-x1),

где k – тангенс угла наклона прямой к оси x –определяется по формуле

k = (f(x1)- f(x2))/(x1 –x2).

Если функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, то при произвольном выборе точек М1 и М2 будем иметь: |k|≤α. Таким образом, с геометрической точки зрения условие Липшица означает ограниченность тангенса угла наклона секущих, проведенных через всевозможные пары точек графика функции y= f(x).

Рис.3. Геометрическая иллюстрация условий Липшица

Сделаем следующий шаг – предположим, что функция f(x) имеет на отрезке [a, b] ограниченную производную: |f’(x)|≤m при xÎ[a, b]. Можно доказать, что в этом случае она удовлетворяет условию Липшица с постоянной α=m. Данное уравнение также имеет простой геометрический смысл- каждой секущей графика функции y= f(x) можно сопоставить параллельную ей касательную (рис. 4). Поэтому наибольший тангенс угла наклона секущих не превосходит наибольшего тангенса угла наклона касательных, и его можно оценить той же константой m: |k|≤m. Таким образом, любая функция f(x) с ограниченной производной обязательно удовлетворяет условию Липшица.

Рис. 4. Геометрическая иллюстрация связи условия Липшица с предположением о дифференцируемости функции f(x)

Сходимость итерационной последовательности к корню уравнения может быть использована для приближенного определения этого корня с любой степенью точности. Для этого нужно только провести достаточное число итераций.

Рассмотрим в качестве примера, иллюстрирующего данный метод, уравнение (10). Его можно представить в следующем виде

tв =45.((82,5- tв)/70)1,4 -20

Роль функции φ(x) в нем играет 45.((82,5- tв)/70)1,4 -20. Это – дифференцируемая функция, которая имеет производную на отрезке [10, 25]. /φ’(x)/ =0,9((82,5 -tв)/70)0,4 ≤ 0,9((82,5-10)/70)0,4

Таким образом, функция удовлетворяет на отрезке [10, 25] условию Липшица с постоянной α =0,9((82,5-10)/70)0,4 <0,912722.

Результаты вычислений по рекуррентной формуле, которая в нашем случае принимает вид xn+1 =45.((82,5- xn)/70)1,4 -20, даны в табл.2. За нулевое приближение была выбрана средняя точка отрезка xo =17,5.

Для удобства анализа итерационной последовательности ее члены расположены по два в строке. В результате образовались столбцы членов с четными и нечетными номерами. Сравнивая их между собой, видим, что четные члены меньше нечетных: итерационная последовательность скачет то вверх, то вниз. С возрастанием номера четные члены возрастают, а нечетные – убывают, приближаясь друг к другу. Такое поведение последовательности означает, что корень уравнения лежит между четными и нечетными итерациями, первые дают его значение с недостатком, вторые - с избытком. Это позволяет легко контролировать точность, достигнутую после любого числа итераций: погрешность не превышает разности между последними вычислениями нечетным и четным членами.

Таблица 2

n X2n X2n+1
  17,5 20,56523134
  17,91260145 20,20519447
  18,22150871 19,93624264
  18,45273279 19,73526403
  18,62577857 19,58504337
  18,75526581 19,47274218
  18,85214805 19,38877819
  18,92462892 19,3259953
  18,97885068 19,27904717
  19,01941101 19,24393831
  19,04975081 19,21768218
  19,0724448 19,19804602
  19,08941941 19,18336044
  19,10211583 19,17237717
  19,11161219 19,16416274

Мы остановили процесс вычисления на 29-й итерации и можем написать для корня с двойное неравенство:

x28 = 19,11161219 <c< x29 = 19,16416274,

т.е. члены итерационной последовательности x28 и x29 определяют с с недостатком и избытком с погрешностью которая не превышает разность x28 - x29:

ε<Δ29 = x28 - x29 <0,05.

Точность, которой мы достигли после 29 итераций, оказалась несколько ниже, чем после 9 шагов в методе вилки. Причина такого различия ясна. В обоих методах погрешность убывает по закону геометрической прогрессии. Для метода вилки знаменатель прогрессии равен ½, он не зависит от вида функции f(x). Для метода итераций знаменатель равен α – постоянная Липшица функции φ(x). В рассматриваемом примере α>1/2, поэтому сходимость итераций медленнее сходимости метода вилки. Это означает, что метод итераций имеет преимущество перед методом вилки с точке зрения скорости сходимости только в том случае, когда α<1/2.





Дата публикования: 2015-07-22; Прочитано: 922 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.005 с)...