Главная > Методы обработки сигналов > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 1. Метод простой итерации и смежные вопросы

Так же как в случае линейных уравнений, начнем изучение итерационных методов с метода простой итерации.

Этот метод состоит в следующем: система уравнений преобразуется к виду

иначе,

и итерации проводятся по формуле

иначе,

Подойдем к изучению этого метода с более общих позиций. Пусть Н — полное метрическое пространство, а оператор отображает Н в себя. Рассмотрим итерационный процесс

решения уравнения

Если при некотором отображение удовлетворяет условию

при всех , то такое отображение называют сжимающим.

Теорема. Если отображение сжимающее, то уравнение имеет единственное решение X и

здесь — расстояние между и .

Доказательство. Согласно (5) имеем

поэтому . При имеем цепочку неравенств

Согласно критерию Коши последовательность имеет некоторый предел X. Переходя к пределу в (6) при , получаем

Справедлива цепочка соотношений

Поскольку произвольное, то , и, следовательно, . Предположим, что уравнение (4) имеет два решения . Тогда . Мы пришли к противоречию. Теорема доказана.

Замечание. При из (6) следует, что . Таким образом, все приближения принадлежат области

При доказательстве теоремы отображение применяется лишь к элементам множества и условие сжимаемости применяется лишь относительно пары элементов из . Поэтому в формулировке теоремы достаточно предполагать лишь, что отображение определено на элементах из и удовлетворяет условию (5) при .

Если решается одно скалярное уравнение, то метод простой итерации имеет простую геометрическую интерпретацию. Построим на плоскости графики . Точки пересечения этих линий соответствуют искомому решению. Если на чертеже имеется точка , то, проведя через нее прямую до пересечения с прямой , а затем прямую до пересечения с кривой , мы получим точку . На рис. 7.1.1 изображено поведение последовательных приближений в случаях: а) . Монотонное поведение при и колебательное при нетрудно усмотреть также из соотношения

В случае системы нелинейных уравнений аналогом метода Зейделя является итерационный процесс, где компоненты приближений определяются из соотношений

Рис. 7.1.1

Нахождение каждого нового значения требует решения, вообще говоря, нелинейного уравнения

с одним неизвестным.

Промежуточное место между итерационными методами (2) и (7) занимает метод, где компоненты приближений определяются из соотношений

Методы (7) и (8) особенно широко использовались в различных моделирующих устройствах, так как они требуют малого объема памяти и просты в реализации.

В достаточно малой окрестности решения X системы для приближений методом простой итерации имеем

где

Таким образом, при приближениях, находящихся в малой окрестности решения, погрешности приближений итерационного процесса (2) (а также и процессов (7) и ) подчиняются примерно тем же законам, что и погрешности итерационных методов решения систем линейных уравнений. Наличие соотношения (9) позволяет производить ускорение сходимости итерационных процессов.

Рассмотрим случай и построим аналог -процесса. При имеющемся приближении обозначим . Согласно (9)

Из этих соотношений получаем

За следующее после приближение примем

Для характеристики методов решения уравнений вводится понятие порядка метода. Говорят, что метод имеет порядок, если существуют такие, что

при условии . Чем больше , тем быстрее сходится процесс итераций при малых значениях , но каждая итерация метода при этом более трудоемка. В связи с этим в вычислительной практике наиболее распространены методы первого и второго порядков (например, метод, определяемый формулой (10), или метод Ньютона, рассматриваемый в следующем параграфе).

Примечание. Иногда в литературе встречается другое, на наш взгляд неразумное, определение порядка метода: говорят, что метод решения системы уравнений имеет порядок , если при его реализации вычисляются производные функций до порядка включительно.

В § 6.10 были рассмотрены итерационные методы решения линейных систем с помощью спектрально-эквивалентных операторов. Аналогичные методы применяются и для решения нелинейных систем. Выбирается оператор такой, что является единственным решением уравнения . Приближения к решению системы определяются из соотношения

Наиболее распространен случай, когда G — линейный оператор. В ряде случаев оператор G выбирается зависящим от , а также от приближения . Тогда в схему (11) укладывается также рассматриваемый ниже метод Ньютона решения нелинейных уравнений.

<< Предыдущий параграф Следующий параграф >>
Оглавление