Геометрическая интерпретация метода 4 страница

- столбец свободных членов

- столбец неизвестных

Решение имеет место, если матрица - неособенная, то есть

- решение системы с помощью обратной матрицы

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

Это обстоятельство обходится с помощью правила Крамера

,

где - определитель матрицы

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

Пример:

Прямой метод

,

По правилу Крамера

Метод Гаусса

Наиболее распространённым приёмом решения системы линейных уравнений является метод Гаусса или метод последовательного исключения неизвестных.

Рассмотрим для простоты систему линейных алгебраических уравнений 4-го порядка:

1. Выбираем ведущий элемент

2. Поделив первое уравнение на , получаем

, (2)

где , ,

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

,

где , ,

4. Выбираем ведущий элемент во втором уравнении

и так далее.

Если , то получим систему

, (3)

то есть матрица имеет диагональный вид:

Из системы 3 отыскиваем следующим образом

, (4)

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

Пример: прежний, но методом Гаусса. Приводит к системе уравнений:

- прямой ход

- обратный ход

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

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

Трудоёмкость метода Гаусса

1. Прямой ход

2. Обратный ход

Общее число выполняемых арифметических действий

то есть для

Предложенный метод Гаусса ориентирован на то, чтобы ведущие элементы не равнялись 0. А если на каком-то шаге возникает ситуация, что ведущий элемент равен 0, то тогда схема “формально” непригодна, хотя заданная система может иметь единственное решение.

Тогда применяют разновидность метод Гаусса. Схема с выбором главного элемента:

1. Выбираем элемент - наибольший по модулю и неявляющийся свободным членом.

2. Вычисляем коэффициенты

, для всех

-тая строка называется главной строкой.

3. Из каждой неглавной строки вычитаем главную строку, умноженную на . В результате получим матрицу, у которой в -ом столбце все коэффициенты нулевые.

4. Преобразуем матрицу следующим образом: отбрасываем - (главную) строку и -й столбец. Получим матрицу .

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

6. Для определения . Объединим все главные строки, начиная с последней. После надлежащего изменения неизвестных получается система с треугольной матрицой.

При работе на ЭВМ при вывод главного элемента может оказаться достаточно трудоёмкой задачей. Поэтому практически в качестве главной строки берут первую строку, а в качестве главного элемента - наибольший по модулю элемент этой строки.

Пример:

Схема Гаусса с выбором главного элемента

		-0,6			-1
I			5			-4	-12	-17
		-0,4				-1
		-0,2		-5		-3		-1
		-0,333		1,6	0,8	-0,4	-1,2	0,8
II		-0,083		0,4	2,2	-2,6	-3,8	-3,8
				-4,8	3,6	-3,8	0,6	-4,4
III		0,571			2,0	-1,665	-1,0	-0,665
					2,5	-2,915	-3,75	-4,165
IV					0,572		1,141	1,713
V							2,0
VI							3,0
VII							-1,0
VIII							1,0

Достоинства метода

1. Если матрица вырождения, то перед исключением неизвестной главный элемент считается равным нулю =>

2. С помощью метода Гаусса можно вычислить определитель треугольной матрицы.

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

В этих случаях для нахождения корней системы лучше пользоваться приближёнными численными методами.

Метод итераций

Дана система уравнений

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

, (2)

где , , или при

, .

Тогда систему уравнений 2 можно записать в виде:

- итерационная формула.

Таким образом, выбрав начальные значения

и так далее.

Итерации останавливаются, когда ,

Сходимость метода итераций для решения системы алгебраических уравнений

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

Если для системы уравнений

выполнено хотя бы одно из условий:

1. ,

2. ,

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

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

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

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

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

Однако, если , то эту систему всегда можно привести к такому виду:

, чтобы удовлетворить условиям 1

Первый способ.

Дано:

Домножим это уравнение на матрицу , где

,

где

Второй способ.

Каждое -ое уравнение делится на

Тогда , , .

Тогда уравнение сходимости имеет вид

,

,

Эти неравенствабудут выполняться, если диагональные элементы будут удовлетворять условиям:

, ,

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

Достоинства метода итераций

1. Если итерации сходятся быстро, то есть для сходимости требуется менее итераций, то выигрыш во времени по сравнению с методом Гаусса:

, - число итераций

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

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

4. Метод итераций легко программируется.

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

Является модификацией метода итераций. Основная идея заключается в том, что при вычислении -го приближения -го корня используются уже вычисленные приближённые корни .

Дано: ,

Выбираем начальное приближение:

На -том шаге, согласно Зейделю строим приближение по следующим формулам:

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

2. Теорема: Для существования единственного решения системы сходимости метода Зейделя достаточно выполнение хотя бы одного из двух условий:

1) ,

2) матрица - симметричная положительно определённая (все её соответственно значения положительны)

Лекция №10

Численное решение систем линейных уравнений

Постановка задачи

Дана система линейных уравнений

(1)

Введём обозначения: вектор - вектор аргументов:

Аналогично вектор функций

Тогда систему 1 можно переписать в виде:

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

Метод Ньютона

Для уравнения имеет вид:

По анологии метод Ньютона для системы линейных уравнений

где - вектор аргументов на -ом шаге итерации

- значения вектора функций (системы уравнений) при

- обратная матрица Якоби

- матрица, Якоби-матрица, состоящая из частных производных

Вполне естественно очевидно, что формулу Ньютона можно применять в том случае, когда Якоби-матрица неособенная, невырождённая, то есть .

Пример:

Дано:

Матрица Якоби

Превоначальная оцнка

1)

2)

3)

- = - =

и так далее

Результаты итераций лучше всего сводить в таблицу

	3,4	0,097	2,2	0,076
	3,497		2,276

Прекращаем вычисления, когда - заданная точность.

Как и в любых численных методах встают следующие задачи: о сходимости метода и о выборе начального значения.

Сходимость метода Ньютона

Вопросами сходимости метода Ньютона занимались такие учёные, как Виллус, Стёпин, Островский, Канторович и другие. Мы же будем рассматривать сходимость, единственность корня и выбор начального условия по Канторовичу. При рассмотрении этих характеристик метода ипользуются понятия нормы. Поэтому прежде дадим определения:

-нормой - называется максимальная сумма модулей элементов по строкам.

-нормой - называется максимальная сумма модулей элементов по столбцам.

-нормой - нызывается квадратный корень из суммы квадратов модулей элементов матрицы

Пример:

Для оценки матриц, используемых в методе Ньютона для нелинейных систем, будем использовать -нормы, а именно