Разработка технических требований и постановка задач выпускной квалификационной работы

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

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

.

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

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

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

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

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

.

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

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

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

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

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

и т. д.

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

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

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

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

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

(2.1).

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

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

(2.2).

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

(2.1').

Матрица.

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

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

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

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

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

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

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

(2.4').

и.

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

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

(2.5).

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

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

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

(2.6).

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

(2.7).

и.

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

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

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

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

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

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

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

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

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

. (2.9).

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

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

(2.10).

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

.

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

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

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

(2.11).

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

(2.12).

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

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

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

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

.

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

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

.

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

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

при .

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

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

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

(2.13) где и ,.

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

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

Положим где.

.

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

(2.14).

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

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

Доказательство. Из формулы (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.19) при любом свободном члене и любом начальном приближении необходимо и достаточно, чтобы все корни уравнения (2.22) удовлетворяли условиям.

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

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

(2.23).

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

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

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

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

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

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

или.

(2.24).

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

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