Решение систем линейных уравнений с помощью метода Зейделя

Размещено на http: //www. allbest. ru/

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. АНАЛИЗ ИТЕРАЦИОННЫХ МЕТОДОВ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

2. РАЗРАБОТКА ТЕХНИЧЕСКИХ ТРЕБОВАНИЙ И ПОСТАНОВКА ЗАДАЧ ВЫПУСКНОЙ КВАЛИФИКАЦИОННОЙ РАБОТЫ

3. РАЗРАБОТКА АЛГОРИТМОВ

4. СОСТАВЛЕНИЕ ПРОГРАММ И ИХ РЕАЛИЗАЦИЯ НА МАТЕМАТИЧЕСКОМ ПАКЕТЕ MATHCAD, ОТЛАДКА, И ЭКСПИРЕМЕНТАЛЬНОЕ ТЕСТИРОВАНИЕ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

Система линейных алгебраических уравнений (линейная система) - это система уравнений, состоящая из алгебраических уравнений первой степени.

В классическом варианте коэффициенты при переменных, свободные члены и неизвестные - это вещественные числа, но все метода и результаты сохраняются (либо обобщаются) на случай любых полей, например, комплексных чисел[1].

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

Системы линейных уравнений широко используются в задачах экономики, физики, химии и др., в том числе линейном программировании.

Решение систем линейных уравнений - одна из основных и классических задач вычислительной линейной алгебры. Хотя задача решения именно системы линейных уравнений сравнительно редко представляет самостоятельный интерес для прикладных задач, но от умения эффективно решать данные системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов решения различных (в особенности - нелинейных) задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма[2].

Способы решения систем линейных уравнений в основном разделяются на две группы:

1) точные методы, представляющие собой конечные алгорифмы для вычисления корней системы (таковы, например, правило Крамера, метод Гаусса, метод главных элементов, метод квадратных корней и др.);

2) итерационные методы, позволяющие получать корни системы с заданной точностью путем сходящихся бесконечных процессов (к числу их относятся метод итерации, метод релаксации, метод Зейделя и др.).

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

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

ВКР состоит из четырех разделов:

1) Анализ итерационных методов решения систем линейных уравнений.

В нем проводится изучение и анализ различных итерационных методов решения линейных уравнений;

2) Разработка технических требований и постановка задач выпускной квалификационной работы. В этом разделе подробно рассматривается решение линейных уравнений методом Зейделя, ставятся задачи ВКР и разрабатываются технические требования;

3) Разработка алгоритмов. В этом разделе разрабатываются алгоритмы модификации метода Зейделя;

4) Составление программ и их реализация на математическом пакете Mathcad, отладка, и экспериментальное тестирование. В последнем разделе составляется, реализуется на математическом пакете Mathcad и отлаживается программа, с помощью которой производится модификация метода Зейделя. Проводится ее тестирование.

1. АНАЛИЗ ИТЕРАЦИОННЫХ МЕТОДОВ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

Методы решения систем линейных алгебраических уравнений делятся на две группы - прямые и итерационные [3].

1. Прямые методы используют определенные соотношения (формулы) для вычисления неизвестных. Они дают решение после выполнения заранее известного количества арифметических операций. Эти методы сравнительно просты и наиболее универсальны, т.е. пригодны для решения широкого класса линейных систем.

Вместе с тем прямые методы имеют и ряд недостатков. Как правило, они требуют хранения в оперативной памяти ЭВМ сразу всей матрицы, и при больших значениях n расходуется много места в памяти. Далее, прямые методы обычно не учитывают структуру матрицы - при большом числе нулевых элементов в разреженных матрицах (например, клеточных или ленточных) эти элементы занимают место в памяти машины, и над ними проводятся арифметические действия. Существенным недостатком прямых методов является накапливание погрешностей в процессе решения, поскольку вычисления на любом этапе используют результаты предыдущих операций. Это особенно опасно для больших систем, когда резко возрастает общее число операций, а так же для плохо обусловленных систем, весьма чувствительных к погрешностям. В связи с этим прямые методы используются обычно для сравнительно небольших с плотно заполненной матрицей и не близким к нулю определителем.

Решение прямых методов выражается в виду точных формул через коэффициенты системы, поэтому иногда их называют точными методами. Но Однако точное решение может быть получено лишь при выполнении вычислений с бесконечным числом (при точных значениях коэффициентов системы). На практике же при использовании ЭВМ вычисления проводятся с ограниченным числом знаков, определяемым разрядностью машины. Поэтому неизбежны погрешности и в окончательных результатах [4].

Среди прямых методов наиболее распространен метод Гаусса; он удобен для вычисления на ЭВМ. Перечислим некоторые другие методы:

1) схема Жордана. При выборе главного элемента не учитывает коэффициенты тех уравнений, из которых уже выбирался главный элемент. Она не имеет преимуществ по сравнению с методом Гаусса. Отметим лишь, что здесь облегчается обратный ход, поскольку система приводится к диагональному виду (а не к треугольному). Эта схема часто используется для нахождения обратной матрицы;

2) метод квадратного корня. Используется в тех случаях, когда матрица системы является симметричной;

3) метод оптимального исключения. Удобен при построчном вводе матрицы системы в оперативную память. Однако построчный ввод имеет и недостатки: частые обращения к внешним устройствам, невозможность выбора главного элемента и др;

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

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

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

Рисунок 1.1 Решение системы линейных уравнений методом итерации

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

Решение систем уравнений при использовании итерационных методов сводится к следующему (рисунок 1.1) [7].

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

Далее подробно рассмотрим метод простой итерации [8].

Пусть дана линейная система

(1.1)

Введя матрицы

Систему (1.1) можно записать в виде уравнения

(1.1')

Предполагая, что диагональные коэффициенты

Решим первое уравнение системы (1.1) относительно x1, второе - относительно х2 и т. д. Тогда получим эквивалентную систему

(1.2)

и при

Введя матрицы

и ,

Систему (1.2) можем записать в матричной форме

(1.2')

Систему (1.2) будем решать методом последовательных приближений. За нулевое приближение принимаем столбец свободных членов

Далее последовательно строим матрицы-столбцы

(первое приближение),

(второе приближение) и т. д.

Любое -е приближение вычисляют по формуле

(1.3)

Если последовательность приближений имеет предел

то этот предел является решением системы (1.2). Переходя к пределу в равенстве (1.3), будем иметь:

т. е. предельный вектор x является решением системы (1.2'), а следовательно, и системы (1).

Напишем формулы приближений в развернутом виде:

(1.3')

Систему (1) иногда выгоднее приводить к виду (1.2) так, чтобы коэффициенты не были равны нулю.

Например уравнение

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

Имея систему

можно положить:

где . Тогда система эквивалентна системе

при

Метод последовательных приближений, определяемых формулой (1.3) или (1.3') называется методом итерации. Процесс итерации (1.3) хорошо сходится, то есть число приближений, необходимых для получения корней системы (1.1) с заданной точностью, невелико, если элементы матрицы малы по абсолютной величине. Иными словами, для успешного применения процесса итерации модули диагональных коэффициентов системы (1.1) должны быть велики по сравнению с модулями недиагональных коэффициентов этой системы (свободные члены при этом роли не играют) [9].

Пример. Решить систему



методом итерации.

Решение: Здесь диагональный коэффициенты 4;3;4 системы значительно преобладают над остальными коэффициентами при неизвестных. Приведем эту систему к нормальному виду (1.2)

(1.5)

В матричной форме систему (1.5) можно написать так:

За нулевые приближения корней системы (4) принимаем:

Подставляя эти значения в правые части уравнений (1.5), получим первые приближения корней:

Далее, подставляя найденные приближения в формулу (1.5) получим вторые приближения корней:

После новой подстановки будем иметь третьи приближения корней:

и т.д.

Результаты вычисления помещены в таблице 1.1.

Таблица 1.1 Результаты вычисления.

0	2	2	5
1	1,92	3,19	5,04
2	1,9094	3,1944	5,0446
3	1,90923	3,19495	5,04485

Замечание: При применении метода итерации (формула (1.3)) нет необходимости за нулевое приближение принимать столбец свободных членов. Как будет доказано ниже, сходимость процесса итерации зависит только от свойств матрицы , причем при выполнении известных условий, если этот процесс сходится пи каком-нибудь выборе исходного начального приближения, то он будет сходится к тому же предельному вектору и при любом другом выборе этого начального приближения. Поэтому начальный вектор в процессе итерации может быть взят произвольным. Целесообразно за компоненты начального вектора выбирать приближенные значения корней системы, находимые грубой прикидкой [10].

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

Отметим, что иногда бывает удобнее подсчитывать не сами приближения, а их разности. Введя обозначения

из формулы (1.3) имеем:

(1.6)

(1.7)

Отсюда, вычитая из равенства (1.6) равенство (1.7), получим:

(1.8)

За нулевое приближение принимаем:

(1.9)

тогда m-е приближение есть

(1.10)

Если, как обычно, положить

,

то равенство (1.8) будет выполнено и при . В противном случае равенство (1.8) при не имеет места. Отсюда вытекает такая методика вычисления этого варианта итерации:

1) если, то

2) если же , то находим

и полагаем

Следовательно,

.

Пример. Решить систему

(1.11)

Решение. Приведем систему (2.11) к виду (2.2):

Здесь

Пользуясь формулами (1.8) и (1.9), получим:

;

;

и т. д.

Таким образом, приближенные значения корней есть

; ;

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

Замечания о точности расчета. Если все коэффициенты и члены длиной системы являются точными числами, то решение ее методом последовательных приближений может быть получено с любым заранее заданным числом m верных десятичных знаков. При этом в значениях последовательных приближений следует удерживать m+1 десятичных знаков и последовательные приближения вычислять до их совпадения, после чего нужно округлить результат на один знак. Если коэффициенты и свободные члены данной системы являются приближенными числами, написанными с p знаками, то решение этой системы производится, как в случае точных чисел, с точностью до m=p знаков [11].

Теорема. Если для приведенной системы (1.2) выполнено по меньшей мере одно из условий

Или

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

Следствие. Для системы

метод итерации сходится, если выполнены неравенства

т. е. если модули диагональных коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов (не считая свободных членов).

Приведение линейной системы к виду, удобному для итерации.

Теорема сходимости накладывает жесткие условия на коэффициенты данной линейной системы

(1.12)

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

, (1.13)

такой, что условия теоремы сходимости будут выполнены.

В самом деле, умножим уравнение (1.12) на матрицу , где -матрица с малыми по модулю элементами. Тогда будем иметь:

, (1.14)

Где

 и .

Если достаточно малы, то очевидно, что система (1.14) удовлетворяет условиям теоремы сходимости [6].

Умножение на матрицу D эквивалентно совокупности элементарных преобразований над уравнениями системы. Задача заключается в том, чтобы прийти к стандартному виду (1.14) с наименьшей затратой труда.

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

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

Пример. Систему

привести к виду, годному для применения метода итерации.

Решение. В уравнении (Б) коэффициент при по модулю больше суммы модулей остальных коэффициентов, поэтому можно принять это уравнение за третье уравнение новой системы. Коэффициент при в уравнении (Г) также больше суммы модулей остальных коэффициентов уравнения (Г), поэтому можно принять это уравнение за первое уравнение новой системы. Таким образом, новая система имеет следующий вид:

Анализируя данную систему, легко заметить, что для получения уравнения (II) с максимальным по модулю коэффициентом при достаточно составить разность (А)-(В):

.

Теперь в новую систему вошли уравнения (А), (Б) и (Г), поэтому в уравнение (IV) обязательно должно войти уравнение (В) данной системы. Подбором убеждаемся, что за уравнение (IV) можно взять линейную комбинацию 2(А)-(Б)+2(В)-(Г), т. е.

.

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



к которой можно применить метод итерации [8].

2. РАЗРАБОТКА ТЕХНИЧЕСКИХ ТРЕБОВАНИЙ И ПОСТАНОВКА ЗАДАЧ ВЫПУСКНОЙ КВАЛИФИКАЦИОННОЙ РАБОТЫ

Одним из самых распространенных итерационных методов, отличающийся простотой и легкостью программирования, является метод Зейделя. Блок-схема алгоритма решения системы линейных уравнений методом Зейделя представлена на рисунке 2. В качестве исходных данных вводятся коэффициенты и правые части уравнений системы, погрешность , допустимое число итераций М, а так же начальные приближения переменных . Отметим, что начальные приближения можно не вводить в ЭВМ, а полагать их равными некоторым значениям (например нулю) [5].

Для удобства чтения блок-схемы объясним некоторые обозначения: k - порядковый номер итерации; i - номер уравнения, а так же переменного, которое вычисляется в данном цикле; j - номер члена вида . Итерации прекращаются либо после выполнения условия

,

либо при k=M. В последнем случае итерации не сходятся, и после М итераций счет прекращается без выдачи результатов. Можно предусмотреть в этом случае также и вывод на печать некоторой поясняющей информации.

Метод Зейделя представляет собой некоторую модификацию метода простой итерации. Основная его идея заключается в том, что при вычислении (k+1)-го приближения неизвестной учитываются уже вычисленные ранее (k+1)-е приближения .

Пусть дана приведенная линейная система:

Выберем произвольно начальные приближения корней

стараясь, конечно, чтобы они в какой-то мере соответствовали неизвестным

Далее предполагая, что k-е приближение корней известно, тогда в соответствии с идеей метода будем строить (k+1) - е приближение по следующим формулам:



Рисунок 2.1 Блок-схема метода Зейделя



.

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

Пример. Методом Зейделя решить систему уравнений

Решение. Приведем эту систему к виду, удобному для итерации,

В качестве нулевых приближений корней возьмем:

Применяя процесс Зейделя, последовательно получим:

и т. д.

Результаты вычислений с точностью до четырех знаков поместим в таблицу 2.1.

Таблица 2.1 Результаты вычислений

0 1 2 3 4 5	1,2000 1,2000 0,9992 0,9996 1,0000 1,0000	0,0000 1,0600 1,0054 1,0001 1,0000 1,0000	0,0000 0,9480 0,9991 1,0001 1,0000 1,0000

Точные значения корней: ; ; .

Случай нормальной системы [3].

Определение. Целый однородный полином второй степени от n переменных называется квадратичной формой этих переменных. В общем случае квадратичная форма имеет вид

(2.1)

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

в n-мерном пространстве.

Если положить

(2.2)

т.е. , то формулу (2.1) короче можно записать следующим образом:

(2.1')

Матрица

(2.3)

носит название матрицы квадратичной формы (2.1'). В силу условия (2.3) матрица А будет симметрической, т.е. совпадет со своей транспонированной матрицей. Наоборот, для всякой симметрической матрицы можно построить соответствующую квадратичную форму (2.1').

Определение. Квадратичная форма (2.3) называется положительно (отрицательно) определенной, если она принимает положительные (отрицательные) значения, обращаясь в нуль лишь при .

Если -положительно определенная квадратичная форма, то уравнение

представляет собой уравнение эллипсоида. Заметим, что в случае

так как

Определение. Назовем линейную систему

(2.4)

нормальной, если: 1) матрица коэффициентов -симметрическая, т.е. , 2) соответствующая квадратичная форма

- положительно определенная.

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

(2.4')

и

Теорема. Если линейная система (2.4)-нормальная, то процесс Зейделя для эквивалентной ей приведенной системы (2.4') всегда сходится.

Доказательство. Пусть линейная система

(2.5)

- нормальная, т.е. матрица - симметрическая и положительно определенная. Положим

- диагональная, - нижняя треугольная,

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

Отсюда

и, следовательно,

(2.6)

Согласно предыдущему процесс Зейделя для системы (2.5) или эквивалентной ей системы (3.6) строится следующим образом:

(2.7)

и

Для сходимости процесса необходимо и достаточно, чтобы все собственные значения матрицы



были по модулю меньше единицы.

В нашем случае имеем:

Пусть -единичный собственный вектор матрицы М, соответствующий собственному значению , т.е.

и следовательно,

Ведем обозначения

( и действительны и ).

Ввиду того, что матрица является транспонированной по отношению к матрице , получаем:



и следовательно,

(2.8)

Используя положительную определенность матрицы А, будем иметь:

. (2.9)

Далее, учитывая положительность числа , очевидно, имеем:

Таким образом, всегда выполнено неравенство

(2.10)

Отсюда для членов дроби (2.8) будем иметь:

.

Теорема доказана.

Способ приведения линейной системы к нормальному виду указывается следующей теоремой [4]

Теорема. Если обе части линейной системы

(2.11)

с неособенной матрицей умножить слева на транспортированную матрицу , то полученная новая система

зейдель программирование mathcad алгоритм

(2.12)

будет нормальной.

Доказательство. Докажем сначала, что матрица есть симметрическая матрица. В самом деле, имеем:

Теперь докажем, что квадратичная, соответствующая матрице ,-положительно определенная. Составим квадратичную форму с матрицей :

Изменяя порядок суммирования, получим:

.

Так как значение суммы не зависит от обозначения индекса суммирования, то

Согласно предположению

.

Поэтому однородная система

имеет лишь нулевые решения. Следовательно,

при .

Теорема доказана.

Необходимые и достаточные условия сходимости процесса Зейделя для системы линейных уравнений [3].

Для линейной системы

(2.13) где и ,

рассмотрим процесс Зейделя

при произвольном начальном векторе

Положим где

, .

Тогда процесс Зейделя в матричном виде можно записать следующим образом:

(2.14)

Теорема. Для сходимости процесса Зейделя (2.14) для системы (2.13) при любом выборе свободного члена и начального вектора необходимо и достаточно, что бы все корни уравнения

 (2.15)

были по модулю меньше единицы.

Доказательство. Из формулы (2.14) вытекает:

(2.16)

Матрица -неособенная, так как

Поэтому равенство (2.16) можно записать в виде

(2.17)

Отсюда ясно, что процесс Зейделя эквивалентен процессу итерации, примененному к линейной системе

Для сходимости итерационного процесса (2.17) необходимо и достаточно, чтобы корни характеристического уравнения

(2.18)

удовлетворяли условиям

Уравнение (2.18), очевидно, равносильно уравнению (2.15).

Замечание. Пусть

. (2.19)

Положим

Для применения метода Зейделя систему (2.19) обычно записывают в форме

(2.20)

Положим

,

Тогда

Где

и

Причем треугольные матрицы В и С реализуют разбиение матрицы системы (2.20), необходимое для применения процесса Зейделя. На основании формулы (2.15) сходимость процесса Зейделя для системы (2.19) зависит от свойств корней уравнения

(2.21)

Уравнение (2.21) можно заменить эквивалентным уравнением

или

(2.22)

Таким образом, для сходимости процесса Зейделя для системы (2.19) при любом свободном члене и любом начальном приближении необходимо и достаточно, чтобы все корни уравнения (2.22) удовлетворяли условиям

Области сходимости процесса обычной итерации и процесса Зейделя, вообще говоря, перекрываются. Можно привести примеры линейных систем, для которых процесс обычной итерации сходится, а процесс Зейделя расходится, и обратно.

Рассмотрим линейную систему

(2.23)

с кососимметрической матрицей

( и действительны).

Характеристическое уравнение матрицы имеет вид

или

Отсюда

Для сходимости метода обычной итерации необходимо и достаточно, чтобы

(область А на рисунке 3).

Для метода Зейделя уравнение, определяющее сходимость, имеет вид

или

(2.24)

Для того что бы корни и уравнения (2.24) удовлетворяли условиям

необходимо и достаточно выполнение неравенств

Откуда

Так как область А и В частично перекрываются, то отсюда следует, что для системы (2.23) можно выбрать коэффициенты и , во-первых, так, чтобы метод итерации сходился, а метод Зейделя расходился (например ; ), и, во-вторых, так, чтобы, наоборот, метод Зейделя сходился, а метод итерации расходился (например, ; ).

Рисунок 2.1 Области сходимости метода простой итерации и метода Зейделя

3. РАЗРАБОТКА АЛГОРИТМОВ

Для разработки алгоритма модификации метода Зейделя, для начала сопоставим его с методом простой итерации:

,

, ,…,-неизвестные, которые подлежат определению из системы (3.1)

, (3.1)

(3,1')

, ,

(3.2')

- задает (начальный вектор)

, ,…, .

,

Основная задача: Найти вектор такой, что

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

(3.3)

Метод Зейделя

(3.4)

Систему (4.4) перепишем в матричной форме:

(3.5)

где матрицы и определяются равенством

, .

Систему (3.5) разрешив относительно , имеем

, (3.6)

Таким образом метод Зейделя решения системы (3.2) эквивалентен методу простой итерации для решения системы

, (3.7)

, .

Далее изучим вероятности сходимости на примере системы двух линейных уравнений

(3.8)

Для системы (3.8) метод простой итерации (3.3) сходится, когда корни , характеристического многочлена

;

(3.9)

удовлетворяют условиям

, . (3.10)

В переменных элементах матрицы

условие (3.10) имеет вид

, (3.11)

Приведенное утверждение мы принимаем для исследования сходимости метода Зейделя.

Для системы (3.8) рассмотрим метод Зейделя

(3.12)

и соответствующий итерационный процесс

(3.13)

В итерационном процессе (3.13) матрица системы имеет вид:

. (3.14)

Вычислим характеристический многочлен этой матрицы:

Итак

. (3.15)

Теперь рассмотрим для системы (3.8) метод Зейделя в следующей форме:

(3.16)

Итерационный процесс (3.16) эквивалентен следующему

(3.17)

Матрица системы (3.17) имеет вид:

Вычислим характеристический многочлен этой матрицы:

Итак

(3.18)

Характеристические многочлены (3.15)

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

Далее перейдем к изучению сходимости метода Зейделя для системы трех уравнений:

(3.19)

Исходя из начального вектора построим последовательность векторов согласно формулам:

(3.20)

Равенства (3.20) в векторной форме имеют вид:

(3.21)

Матричное равенство (3.21) умножаем на матрицу

.

Для описания всевозможных случаев применения метода Зейделя к решению системы (3.19) опишем метод построения матриц Р, которые имеют в каждой строке и в каждом столбце по одному не нулевому элементу, равному 1.

Пусть перестановка чисел (1, 2, 3). Например, может быть одна из перестановок (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).

Элементы матрицы Р определим по формуле

Например, , , . Тогда

При , , имеем

Заменим в системе (3.19):

,

получим систему:

(3.22)

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

Имея матрицы:



Можно их перемножить, но в случае умножения данных матриц, выполняется условие

(3.23)

Перемножив матрицы А и В

получаем матрицу

, (3.24)

которая является единичной матрицей.

Далее распишем всевозможные варианты матриц Р:

,,,,

.

Перемножая между собой матрицы , , , , и , и получая аналогичные, заполним таблицу 3.1:

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

,,

Таблица 3.1 Возможные матрицы Р и их произведения друг на друга.

,

,,

,,

.

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

Определяется величиной , где - собственное значение матрицы ). Число (возможно комплексное) называется собственным значение матрицы , если уравнение

;

имеет ненулевое решение; Это ненулевое решение называется собственным вектором матрицы .

4. СОСТАВЛЕНИЕ ПРОГРАММ И ИХ РЕАЛИЗАЦИЯ НА МАТЕМАТИЧЕСКОМ ПАКЕТЕ MATHCAD. ОТЛАДКА И ЭКСПИРЕМЕНТАЛЬНОЕ ТЕСТИРОВАНИЕ

1) Создадим программу, которая будет создавать поддиагональную матрицу , матрице ;

2) Далее алгоритм замены x на Py;

3) Посчитаем собственные значения матрицы ;

4) Посчитаем собственные значения, получившейся матрицы ;

5) Напишем программу, которая создает матрицы, имеющие по одному ненулевому элементу в каждой строке и в каждом столбце;



6) Далее путем ввода положений ненулевых элементов в матрицу получаем 5 разных матриц с ненулевыми элементами;

7) К каждой матрице находим собственные значения, с помощью команды eigenvals;

8) Сравниваем и анализируем полученные значения.

Далее обратимся к математическому пакету Mathcad, для реализации данной идеи, ее отладке и экспериментальному тестированию. Отобразим все на рисунках 4.1 - 4.5.



Реализация модификации метода Зейделя в математическом пакете Mathcad



Реализация модификации метода Зейделя в математическом пакете Mathcad

Реализация модификации метода Зейделя в математическом пакете Mathcad.



Реализация модификации метода Зейделя в математическом пакете Mathcad

Реализация модификации метода Зейделя в математическом пакете Mathcad. Собственные значения некоторых матриц, оказались меньше, что говорит о том, что при определенной перестановке уравнений системы, система будет сходиться быстрее.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Александров, А. Д. Математика: её содержание, методы и значение: учебник для вузов: в 3 т. Т. 3 / А. Д. Александров, А. Н. Колмогоров, М. А. Лаврентьев. - Москва: АН СССР, 1956. - 336с.

2. Бабич, В. М. Линейные уравнения математической физики. Справочная математическая библиотека: учеб. пособие / В.М. Бабич, М.Б. Капилевич, С.Г. Михлин. - Москва: Гостехиздат, 2012. - 367 c.

3. Демидович, Б. П. Основы вычислительной математики: учеб. пособие / Б. П. Демидович, И. А. Марон. - Москва: Наука, 1970. - С. 294 - 328.

4. Соколов, Н. П. Пространственные матрицы и их приложения: монография / Н. П. Соколов. - Москва: Государственное издательство физико-математической литературы, 1960. - 299 с.

5. Турчак, Л. И. Основы численных методов: учеб. пособие / Л. И. Турчак. - Москва: Наука, 1987. - С. 114-154.

6. Чивилихин, С.А. Вычислительные методы в технологиях программирования. Элементы теории и практикум: учеб. пособие / С. А. Чивилихин. - СПб: СПбГУИТМО, 2008. - 108 с.

7. Вержбицкий, В. М. Основы численных методов: учеб. пособие / В. М. Вержбицкий. - Москва: Высшая школа, 2005. - 840 с.

8. Воеводин, В. В. Численные методы алгебры. Теория и алгоритмы: учеб. пособие / В. В. Воеводин. - Москва: Наука, 1966. - 303 с.

9. Самарский, А. А. Численные методы: учеб. пособие / А. А. Самарский, А. В. Гулин. - Москва: Наука, 1989. - 568 c.

10. Семушин, И.В. Численные методы алгебры: учеб. пособие / И. В. Семушин. - Ульяновск: УлГТУ, 2006. - 230 c.

11. Райс, Дж. Матричные вычисления и математическое обеспечение / Дж. Райс. - Москва: Мир, 1984. - 440 с.

Размещено на Аllbest.ru

...