Методы решения системлинейных уравнений
1. Решениесистемы линейных уравнений методом Гаусса
Задачи аппроксимациифункции, а также множество других задач прикладной математики м вычислительнойфизики сводятся к задачам о решении систем линейных уравнений. Самымуниверсальным методом решения системы линейных уравнений является методпоследовательного исключения неизвестных, называемый методом Гаусса.
Дляиллюстрации смысла метода Гаусса рассмотрим систему линейных уравнений:
/> (1)
Эту систему запишем вматричном виде:
/> (2)
Как известно, обе частиуравнения можно умножить на ненулевое число, а также можно из одного уравнениявычесть другое. Используя эти свойства, постараемся привести матрицу системы(2) к треугольному виду, т.е. к виду, когда ниже главной диагонали все элементы– нули. Этот этап решения называется прямым ходом.
На первом шаге прямогохода умножим первое уравнение на /> и вычтем из второго, тогдаисключится переменная /> из второго уравнения. Затем,умножим первое уравнение на /> и вычтем из третьего, тогдасистема (2) преобразуется в систему вида:
/> (3)
На втором шаге прямогохода из третьего уравнения исключаем />, т.е. из третьего уравнениявычитаем второе, умноженное, на />, что приводит систему (3) ктреугольному виду (4)
/> (4)
Систему (4) переписываемв привычном виде:
/> (5)
Теперь, из системы (5)можем находить решение в обратном порядке, т.е. сначала находим из третьегоуравнения />,далее, подставляя во второе уравнение, находим />. Подставляя /> и /> в первое уравнениесистемы (5), находим />. Нахождение решения /> из системы (5)называют обратным ходом.
Теперь, на основерассмотренного примера, составим общий алгоритм метода Гаусса для системы:
/> (6)
Метод Гаусса состоит издвух этапов:
а) прямой ход – когдаматрица системы (6) приводится к треугольному виду;
б) обратный ход – когдапоследовательно вычисляются неизвестные в обратном порядке, т.е. впоследовательности: />.
а) Прямой ход: дляприведения системы (6) к треугольному виду, уравнения с ненулевымикоэффициентами при переменной /> переставляются таким образом,чтобы они были выше, чем уравнения с нулевыми коэффициентами />. Далее, вычитаем первоеуравнение, помноженное на />, из второго уравнения, вычитаемпервое уравнение, помноженное на />, из третьего уравнения и т.д. Вобщем, вычитаем первое уравнение, помноженное на />, из /> - го уравнения при />, если />. Вследствие этой процедуры,мы обнулили все коэффициенты при переменной /> в каждом из уравнений, начиная совторого, т.е. система (6) принимает вид:
/> (7)
Далее, применяем тужесамую процедуру, для уравнений системы (7), начиная со второго уравнения, т.е.первое уравнение исключается из «игры». Теперь стараемся обнулить коэффициентыпри переменной />, начиная с третьего уравнения ит.д., пока не приведём систему к треугольному виду. Если />, то система всегдаприводима (теоретически) к треугольному виду. Общий алгоритм прямого хода можнопредставить в виде:
/> (8)
б) Обратный ход:Вычисляем неизвестные по формулам:
/> (9)
Замечание: для вычисления определителясистемы можно использовать треугольную форму полученной матрицы, тогдаопределитель этой матрицы равен произведению диагональных элементов, т.е.
/> (10)
2. Метод Гаусса с выборомглавного элемента
Метод Гаусса настолькоуниверсален, что для некоторых систем получаются практически «плохие»результаты, поэтому разрабатываются различные хитрые выходы из ситуации. Вслучае, когда некоторые коэффициенты матрицы системы близки между собой, какизвестно относительные погрешности сильно возрастают при вычитании, поэтомуклассический метод Гаусса даёт большие погрешности. Чтобы обойти эту трудность,стараются в прямом ходе Гаусса выбрать то уравнение, у которого коэффициент при/> максималени в качестве основного «игрока» выбирают именно это уравнение, тем самым обходятрудности вычитания близких чисел (если это возможно). Далее, когда нужнообнулить все коэффициенты переменной />, кроме одного уравнения – этимособым уравнением опять выбирают то уравнение, у которого коэффициент при /> максимальный ит.д., пока не получим треугольную матрицу.
Обратный ход происходиттак же, как и в классическом методе Гаусса.
3. Оценка погрешности прирешении системы линейных уравнений
Для того, чтобы оценитьпогрешности вычислений решения системы линейных уравнений, нам нужно ввестипонятия соответствующих норм матриц.
Прежде всего, вспомнимтри наиболее часто употребляемые нормы для вектора />:
/> (11)
/>(Евклидова норма) (12)
/>(Чебышевская норма) (13)
Для всякой нормы векторовможно ввести соответствующую норму матриц:
/> (14)
которая согласована снормой векторов в том смысле, что
/> (15)
Можно показать, что длятрёх приведённых выше случаев нормы матрицы /> задаются формулами:
/> (16)
/> (17)
/> (18)
Здесь /> - являютсясингулярными числами матрицы />, т.е. это положительные значенияквадратных корней /> - матрицы /> (которая являетсяположительно-определённой матрицей, при />).
Длявещественных симметричных матриц /> - где /> - собственные числа матрицы />.
Абсолютнаяпогрешность решения системы:
/> (19)
где /> - матрицасистемы, /> -матрица правых частей, оценивается нормой:
/> (20)
Относительнаяпогрешность оценивается по формуле:
/> (21)
где />.
4.Итерационные методы решения систем линейных уравнений
Рассмотрим системулинейных уравнений, которая плохо решается методами Гаусса. Перепишем системууравнений в виде:
/> (22)
где /> - заданнаячисловая матрица />-го порядка, /> - заданный постоянныйвектор.
4.1 Методпростой итерации Якоби
Этот методсостоит в следующем: выбирается произвольный вектор /> (начальное приближение) истроится итерационная последовательность векторов по формуле:
/>, /> (23)
Приведём теорему, дающуюдостаточное условие сходимости метода Якоби.
Теорема. Если />, то система уравнений(22) имеет единственное решение /> и итерации (23) сходятся крешению.
Легко заметить,что эта теорема является простым обобщением теоремы о сжатых отображенияхизученных нами раньше для одношагового итерационного процесса в общем виде. Всеоценки, полученные ранее, переносятся и для системы уравнений, разница лишь впонятиях соответствующих норм. Обобщая метод простой итерации Якоби для случаясистемы уравнений:
/> (24)
Строималгоритм решения:
а)переписываем уравнение (24) в однородном виде и умножаем на постоянную /> - которуюдалее найдём из условий сходимости итерационного процесса:
/> (25)
б) добавляем /> к обеим частям(25) и получаем:
/> (26)
в) строим итерационнуюформулу Якоби:
/> (27)
гдепостоянную /> находимиз условий сходимости итерационного процесса (27), который в данном случаеимеет вид:
/> (28)
где /> -вектор-функция из (26) или исходя из теоремы о сжатых отображениях />, где /> - единичнаяматрица.
Рассмотримчисловой пример:
Пусть имеемсистему уравнений:
/>
Переписываемсистему в виде:
/>
Составляемитерационную формулу:
/>
Коэффициент /> выбираем изусловий: />,т.е.
/>
/>.
4.2 МетодГаусса-Зейделя
Для решения линейнойсистемы уравнений разработано множество итерационных методов. Тем более, чтометод простой итерации Якоби сходится медленно. Одним из таких методов являетсяметод Гаусса-Зейделя.
Дляиллюстрации метода рассмотрим числовой пример:
/> (29)
Уравнения переписанытаким образом, что на главной диагонали стоят максимальные для каждогоуравнения коэффициенты.
Начинаем сприближения />.Используя первое уравнение, находим для /> новое значение /> при условии />.
/> (30)
Беря этозначение /> и/> извторого уравнения, находим />, далее из третьего уравнениянаходим />, />. Эти тривеличины дают новое приближение и можно повторить цикл с начала, получаем: />, />, /> и т.д.Итерации продолжаются до выполнения неравенства />.
Общийалгоритм метода Гаусса-Зейделя имеет вид:
Пусть
/> (31)
где у матрицы/> - вседиагональные элементы отличны от нуля, т.е. /> (если />, тогда переставляем строки так,чтобы добиться условия />). Если />-ое уравнение системы (31)разделить на />, а затем все неизвестные кроме /> - перенести вправую часть, то мы придём к эквивалентной системе вида:
/> (32)
где />, />, />
/> (33)
Метод Гаусса-Зейделясостоит в том, что итерации производятся по формуле:
/> (34)
где /> - номеритерации, а />.
Замечание: для сходимости метода(34) достаточно выполнения хотя бы одного из условий:
а)
/>, /> (35)
б) /> - симметричная иположительно-определённая матрица.
5. Решение системы линейныхуравнений методом Ритца
Если /> - симметричная иположительно-определённая матрица, то задача решения линейной системыуравнений:
/> (36)
эквивалентна задаченахождения точки минимума функции многих переменных:
/> (37)
где скалярныепроизведения понимаются в смысле />, т.е.
/> (38)
Иначе говоря, решениесистемы линейных уравнений (36) доставляет минимум функции многих переменных:
/> (39)
И наоборот, точкаминимума функции (39) является решением системы линейных уравнений (36).
Таким образом, методРитца позволяет решение линейной системы уравнений с симметричной иположительно-определённой матрицей свести к задаче нахождения точки минимумафункций многих переменных. А эту задачу мы уже умеем решать.
6. Решение системылинейных уравнений с трехдиаганальной матрицей методом прогонки Томаса
При решениизадач конечно-разностными методами или методом конечных элементов, часторешение задачи сводится к решению линейной системы уравнений с трехдиаганальнойматрицей коэффициентов, т.е. с матрицей, где все элементы нули, кроме трехдиагоналей (в окрестности главной диагонали); рассмотрим систему стрехдиаганальной матрицей:
/> (40)
для решенияэтой линейной системы уравнений, конечно, можно применять метод Гаусса, нотогда пришлось бы делать много необязательных операций с нулями. Чтобысэкономить время вычислений и не работать лишний раз с нулями, Томас (1949г.)разработал специальный алгоритм расчета. Рассчитывая по алгоритму Томасаэлементы получаемой треугольной матрицы, мы следуем методу Гаусса, суточнением, что с нулями никаких действий не производим; алгоритм Томасаназывают – методом прогонки.
Для решениясистемы (40) методом прогонки – Томаса действуем следующим образом:
а) прямойход:
/> (41)
Замечание:после проведения прямого хода предполагается, что все />, и /> — неизменны (что очевидно).
б) обратныйход:
/> (42)
Таким образом, длясистемы линейных уравнений с трехдиаганальной матрицей наиболее экономнымявляется алгоритм прогонки – Томаса, который является «отфильтрованным» методомГаусса.
Метод минимизации невязкидля решения линейной системы уравнений (метод наименьших квадратов).
При проведенииэкспериментов, часто приходится решать следующую задачу: определить />известных />, которыенепосредственно не измеряются, а измеряются величины /> связанные с определяемымипеременными />.Измерения не свободны от случайных ошибок, которыми нельзя пренебречь.
Числонаблюдаемых величин больше числа неизвестных />. Пусть известно, что величины /> связаны междусобой линейной зависимостью:
/>, />, />. (43)
Коэффициенты /> - считаютсяизвестными и неотягощенными случайными ошибками. Система (43) называетсясистемой условных уравнений.
Если бы всечисла /> былиточными, то неизвестные />, /> могли бы быть определены из любых/> -уравнений системы />. Но так, как /> - определены сошибками, то система условных уравнений несовместна (переопределена, т.к. />), существуют«невязки»:
/>, /> /> (44)
задача теперьзаключается в том, чтобы найти такие значения />, при которых функция невязки /> - минимальнопо некоторой норме, т.е. мы ищем такие />, при которых норма невязки /> - минимальна.
В методенаименьших квадратов, в качестве нормы рассматривают дискретную норму Гаусса:
/> (45)
Очевидно, чтоэта норма минимальна тогда, когда минимально подкоренное выражение, т.е. суммаквадратов невязок />.
/> (46)
Условиясуществования минимума для функций специального вида /> имеют вид:
/>,/>, (47)
т.е. задачасводится, как и в общей теории приближений, к решению системы нормальныхуравнений.
Для примерарассмотрим />уравненийс тремя неизвестными, система условных уравнений имеет вид:
/> (48)
Тогда системасоответствующих нормальных уравнений имеет вид:
/> (49)
Решение системы (49) даетрешение задачи (48) наилучшим приближением, в смысле дискретной нормы Гаусса.
Замечания:
1) классический методГаусса, метод Гаусса с выбором главного элемента, метод Якоби и методминимизации невязки являются общими методами и применяются для определениярешения невырожденных систем линейных уравнений, когда ведущие (большие помодулю) элементы матрицы системы расположены в окрестности главной диагонали(система хорошо обусловлена), если же система плохо обусловлена, тогда нужноменять соответствующую модель, чтобы она приводила к приемлемой системеуравнений;
2) дляускорения сходимости методов разработаны специальные методы – методГаусса-Зейделя, методы релаксации и др., которые применимы лишь для узкогокласса систем – с симметрической, положительно-определенной матрицей; сненулевыми диагональными элементами;
3) для нуждразностных уравнений разработаны специальные алгоритмы прогонки Томаса, которыеявляются «экономными» методами Гаусса для трехдиагональных матриц системылинейных уравнений.
Литература
1. Т. Шуп. Решениеинтегральных задач на ЭВМ. Мир., М.,2002
2. Л. Коллатц, Ю. Альберхт.Задачи по прикладной математике. Мир., М.,1998.
3. Т.А. Обгадзе. Элементыматематического моделирования. Учебное пособие. Грузинский ПолитехническийИнститут им. В.И. Ленина, Тбилисси, 1999.