Реферат: Нахождение корней уравнения методом простой итерации (ЛИСП-реализация)

x^(k+1) =φ(x^(k) ), k=0, 1, 2, ... (2.3)

начиная с приближения x⁽⁰⁾ .

УТВЕРЖДЕНИЕ: 1 Если последовательность {x^(k) } метода простой итерации сходится и функция φ непрерывна, то предел последовательности является корнем уравнения x=φ(x)

ДОКАЗАТЕЛЬСТВО: Пусть

. (2.4)

Перейдем к пределу в равенстве x^(k+1) =φ(x^(k) ) Получим с одной стороны по (2.4), что а с другой стороны в силу непрерывности функции φ и (2.4)

.

В результате получаем x^* =φ(x^* ). Следовательно, x^* - корень уравнения (2.2), т.е. X=x^* .

Чтобы пользоваться этим утверждением нужна сходимость последовательности {x^(k) }. Достаточное условие сходимости дает:

ТЕОРЕМА 2.1: (о сходимости) Пусть уравнение x=φ(x) имеет единственный корень на отрезке [a,b] и выполнены условия:

1) φ(x) C¹ [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⁽⁰⁾ [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 ² | x ^(k-1) - x ^(k-2) | ≤ ... ≤ q ^k | x ⁽¹⁾ - x ⁽⁰⁾ |. (2.5)

Рассмотрим ряд

S_∞ = x ⁽⁰⁾ + ( x ⁽¹⁾ - x ⁽⁰⁾ ) + ... + ( x ^(k+1) - x ^(k) ) + ... . (2.6)

Если мы докажем, что этот ряд сходится, то значит сходится и последовательность его частичных сумм

S_k = x ⁽⁰⁾ + ( x ⁽¹⁾ - x ⁽⁰⁾ ) + ... + ( x ^(k) - x ^(k-1) ).

Но нетрудно вычислить, что

S_k = x ^(k)) . (2.7)

Следовательно, мы тем самым докажем и сходимость итерационной последовательности {x^(k) }.

Для доказательства сходимости pяда (2.6) сравним его почленно (без первого слагаемого x⁽⁰⁾ ) с рядом

q ⁰ | x ⁽¹⁾ - x ⁽⁰⁾ | + q ¹ |x ⁽¹⁾ - x ⁽⁰⁾ | + ... + |x ⁽¹⁾ - x ⁽⁰⁾ | + ..., (2.8)

который сходится как бесконечно убывающая геометрическая прогрессия (так как по условию q < 1). В силу неравенства (2.5) абсолютные величины ряда (2.6) не превосходят соответствующих членов сходящегося ряда (2.8) (то есть ряд (2.8) мажорирует ряд (2.6). Следовательно ряд (2.6) также сходится. Tем самым сходится последовательность {x⁽⁰⁾ }.