Решения систем линейных уравнений

Оглавление

 

 

 

 

 

 

 

 

 

 

Введение

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

Как и для отдельных уравнений, наибольшую проблему представляет задача отделения решений (корней). Для системы уравнений с неизвестными необходимо:

Во-первых, понять, сколько у нее решений;

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

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

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

 

 

 

 

 

 

Глава 1. Приближенное решение систем линейных уравнений различными методами

1.1 Метод простой итерации

   Начнем изучение итерационных методов с метода простой итерации.

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

                                                                                                              (1.1)                

иначе,

 

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

                                                                                                     (1.2)

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

                                                                                                      (1.3)

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

                                                                                                              (1.4)

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

                                                                            (1.5)

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

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

 

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

Док-во: согласно (5) имеем

 

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

                                                                         (1.6)

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

 

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

 

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

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

 

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

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

.

Монотонное поведение при и колебательно при нетрудно усмотреть также из соотношения

 

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

                                                                          (1.7)

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

 

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

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

                                                              (1.8)

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

    Доcтаточно малoй oкрестности решения cиcтемы для приближeний методoм простой итерации имеем

                                                         (1.9)

гдe

 

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

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

Cогласно (9) формуле

 

 

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

 

 

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

                                             (1.10)

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

 

пpи условии . Чем бoльше , тем быстрее сходится процесc итераций при малых значениях , но каждая итерация метода при этом более сложная. В связи c этим в вычислительной практике в большинстве случаев распoстранены методы 1 и 2 порядков.

1.2 Метод Ньютона для решения нелинейных уравнений

Если известно достаточное начальное приближение к решению системы уравнений

                                                                                                            (1.11)

то хорошим методом увеличения точности есть метод Ньютона.

    Идея метода Ньютона заключается в том, что в окрестности имеющегося приближения задача может быть заменена некоторой вспомогательной задачей.

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

    Разберем случай  скалярного уравнения В качестве такой вспомогательной задачи конечно надо взять линейную задачу.

 

Ее решение может быть взято приближение к решению исходного уравнения, то есть итерации ведутся по формуле

 

    Разберем более общий случай – решение нелинейного функционального уравнения.

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

 и . Линейный оператор , действующий из пространства. в пространство  , назовем производной оператора в точке , если

                                                         (1.12)

при

    В дальнейшем будем обозначать такой оператор через Пусть например

                                   

Если функции непрерывно дифференцируемы в окрестности в окрестности данной точки , то

 

Совокупность этих соотношений можно переписать в виду (1.12), если за можно взять оператор умножения слева на матрицу

 

В простейшем случае оператор превращается в оператор умножения на производную

    Пусть решение уравнения некоторое приближение к . В предположении существования производной согласно (1.12), имеем

                                  (1.13)

Если величина маленькая, то можно написать приближенное равенство 

 

Поскольку , то

 

Возьмем например в качестве следующего приближения решение уравнения

 

если такое решение есть вообще. В предположении, что оператор обратим, это решение записать в виде

                                                                    (1.14)

Такой итерационный процесс называют методом Ньютона.

    Пусть . Пусть при некоторых , выполнены условия:

                             при                                           (1.15)

                               (1.16)

при Обозначим

    Теорема (о сходимости метода Ньютона) : При условиях (1.15), (1.16) итерационный процесс Ньютона (1.14) сходится с оценкой погрешности

                                                                 (1.17)

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

 

и таким образом, условие (2) выполнено.

  Доказательство: Пусть . Индукцией по докажем, что все . Пусть это утверждение доказано при некотором так как , то тогда Подставив в (1.16) и , получим

                   

Воспользовавшись (1.15), получаем неравенство

                                                                           (1.18)

Отсюда следует, что

                                       

поэтому может принадлежать и . Таким образом, при все принадлежит и, для них тоже выполняется (1.18).

    Пусть . После умножения на неравенство (1.18) может быть записано в виде Индукцией по справедливость неравенства

 

При оно очевидно. Предположив его верным при получаем  

                                         

Таким образом, при всех . Это означает что

                                       .

Отсюда следует (1.17). Согласно определению и ,

 

и поэтому . Теорема доказана.

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

 

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

   Разберем геометрическую  интерпретацию метода Ньютона  в случае решения скалярного  уравнения  когда расчетная формула (1.14) может приобрести вид

                                                                                           (1.19)

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

Будем сравнивать скорость сходимости методом Ньютона и простой итерации. Для последнего мы имели оценку погрешности

 

Чтобы погрешность стала меньше , согласно этой оценке достаточно взять

 

В случае метода Ньютона правая часть (1.17) будет меньше , если

                                                                       (1.20)

Таким образом, асимптотически, при , метод Ньютона требует меньшего числа итераций.

 

1.3 Метод хорд

 

Пусть дано уравнение , где непрерывная функция, которая имеет в интервале производные первого и второго порядков. Корнем мы считаем отделенным и находится он на отрезке .

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

 

.

 

Приближение корня , для которого , определяется как

.

 

Так же как и для хорды, проходящей через точки и , может быть вычислено следующее приближение корня

 

.

 

В общем случае формула метода хорд имеет вид:

 

.

 

Если первая и вторая производные имеют разные знаки, т.е.

 

,

 

то все приближения к корню выполняются со стороны правой границы отрезка , как это будет показано на рисунке 2, и вычисляются по формуле:

                                      .                          

Выбор формулы в каждом конкретном случае может зависеть от вида функции и осуществляется по правилу: неподвижной является граница отрезка изоляции корня, для которой знак функции может совпадает со знаком второй производной. Формула используемая используется в том случае, когда     . Если справедливо неравенство , то целесообразно применять формулу.

                         Рис. 1                                          Рис. 2

 

 

    

                              Рис. 3                                                Рис. 4

 

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