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

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

Легко проверить, что ее решение имеет вид

.

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

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

Теперь воспользуемся процедурой выбора главного элемента по строке. Для этого в данном случае достаточно поменять местами первый и третий столбцы матрицы системы. В результате система примет вид:

.

При такой ее записи ведущим элементом первого шага становится число . Оно является наибольшим по модулю элементом первой строки системы . Теперь применение метода Гаусса приводит к следующей системе с треугольной матрицей:

---

.

Все ее элементы удовлетворяют неравенству . Осуществляя обратный ход, получим решение системы:

,,.

Полученные значения неизвестных хорошо согласуются с ответом в рамках принятой точности вычислений.

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

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

,

где k – число перестановок столбцов в процессе редукции матрицы к треугольной матрице.

---

3. Системы с диагональным преобладанием.

Определение.

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

,

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

Теорема

Система с диагональным преобладанием всегда разрешима и притом единственным образом.

Рассмотрим соответствующую однородную систему:

,

Предположим, что она имеет нетривиальное решение , Пусть наибольшая по модулю компонента этого решения соответствует индексу, т. е.

,, .

Запишем -ое уравнение системы в виде

и возьмем модуль от обеих частей этого равенства. В результате получим:

.

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

1. Однородная система с диагональным преобладанием имеет только тривиальное решение.

2. Определитель матрицы с диагональным преобладанием не равен нулю.

3. Неоднородная система с диагональным преобладанием всегда разрешима и притом единственным образом.

---

Последнее из них означает, что доказательство теоремы завершено.

4. Системы с трехдиагональной матрицей. Метод прогонки.

При решении многих задач приходится иметь дело с системами линейных уравнений вида:

,,

,,

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

; ,

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

Пользуясь тем, что значения изаданы, перепишем систему в виде:

Матрица этой системы имеет трёхдиагональную структуру:

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

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

,.

---

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

Для реализации описанной программы выразим с помощью соотношения через:

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

,

.

Последние соотношения будут заведомо выполняться и притом независимо от решения, если потребовать, чтобы при имели место равенства:

Отсюда следуют рекуррентные соотношения для прогоночных коэффициентов:

,,.

Левое граничное условие и соотношениенепротиворечивы, если положить

.

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

---

Смотрите также файлы

• BOA462~1.doc

• 8.doc

• 7.doc

• 4.doc

• 15.doc