Н.Н. Калиткин - Численные методы (1133437), страница 27
Текст из файла (страница 27)
Итерационные методы приведены в 5 3; они выгодны для систем специального вида, со слабо заполненной матрицей очень большого порядка и 10' — 110'. Сравнительно недавно для решения плохо обусловленных систем стали применять методы регуляризации. системы углвнения !Гл. ч 2. Метод исключения Гаусса, Как известно из курса линейной алгебры, решение системы линейных уравнений можно выразить по правилу Крамера через отношение определителей. Но этот способ неудобен для вычислений, ибо определитель найти не проще, чем непосредственно решить исходную систему а„х, + а„х, +... + а,„х„= Ь„ а„х,+а„х,+...+а,„х„=Ь„ а„,х,+а„,х,+...+а„„х„= Ь„ нли короче л ,У, 'амх„= Ьь 1:- !' ~ и.
А=! Далее мы увидим, что решить эту систему можно примерно за 9),и' арифметических действий. Но даже если использовать для вычисления определителей наиболее быстрый метод, описанный в п.З, то для нахождения всех требуемых по правилу Крамера определителей надо '!,и! действий! Таким образом, формула Крамера удобна для теоретического исследования свойств решения, но очень невыгодна для его численного нахождения. Начнем исследование системы (1) с частного случая, когда численное решение находится особенно просто. Пусть матрица системы треугольная, т.
е. все элементы ниже главной диагонали равны нулю, Тогда из последнего уравнения сразу определяем х„. Подставляя его в предпоследнее уравнение, находим х„ и т. д. Общие формулы имеют вид если а„=О при й 1. Метод Гаусса для произвольной системы основан на приведении матрицы системы к треугольной.
Вычтем из второго уравнения системы (1) первое, умноженное на такое число, чтобы уничтожился коэффициент при х,. Затем таким же образом вычтем первое уравнение из третьего, четвертого и т. д. Тогда исключатся все коэффициенты первого столбца, лежащие ниже главной диагонали. Затем при помощи второго уравнения исключим из третьего, четвертого и т. д. уравнений коэффициенты второго столбца. Последовательно продолжая этот процесс, исключим из матрицы все коэффициенты, лежащие ниже главной диагонали. Запишем общие формулы процесса.
Пусть проведено исключение коэффициентов из А — 1 столбца. Тогда остались такие 129 ЛИНЕННЫЕ СИСТЕМЫ уравнения с ненулевыми элементами ниже главной диагонали: и Я а!!!Дх1=(!!31, lгм=:!'(и. (3) / э Умножим е-ю строку на число С „=а~">/а~ф1, и лК (4) и вычтем из т-й строки. Первый ненулевой элемент этой строки обратится в нуль, а остальные изменятся по формулам а!'+ '! = а!"! — с а!'! л! т! и» и! (5) Х сл ю амх„= Ь,, э=! 1.=-! ==л, (6) а "л а'!' ы !! ~и\ 12! лм ам ~и! с„! аа! а "л !л !1! ап ии алл 6'" и Ь!л! ! лм л! лил л! а!"! !и! Ллт или или "' ~ил Ьл Треугольная система (6) легко решается обратным ходом по формулам (2), в которых всем коэффициентам надо приписать вверху (в скобках) индекс строки. Сделаем несколько замечаний. Исключение по формулам (4) †(5) нельзя проводить, если в ходе расчета на главной диагонали оказался нулевой элемент а<~> = О.
Но в первом столбце промежуточной системы (3) все элементы не могут быть нулями: это означало бы, что бе! А =О. Перестановкой строк можно переместить ненулевой элемент на главную диагональ и продолжить расчет. Производя вычисления по этим формулам при всех указанных индексах, исключим элементы л-го столбца. Будем называть такое исключение циклом процесса. Выполнение всех циклов называется прямым ходом исключения.
Запишем треугольную систему, получакецуюся после выполнения всех циклов. При приведении системы к треугольному виду освободятся клетки в нижней половине матрицы системы ()). На освободившиеся места матрицы поставим множители с „; их следует запоминать, ибо они потребуются при обращении матрицы или уточнении решения. Получим [зо СИСТЕМЫ УРАВНЕНИЯ [ГЛ. У Если элемент на главной диагонали а[Д мал, то эта строка умножается на большие числа с ы что приводит к значительным ошибкам округления при вычитаниях. Чтобы избежать этого, каждый цикл всегда начинают с перестановки строк. Среди элементов столбца а[[А[, т- я, находят главный, т.
е, наибольший по модулю в й-м столбце, и перестановкой строк персводят его на главную диагональ, после чего делают исключения. В методе Гаусса с выбором главного злеменпи[ погрешность округления обычно невелика. Только для плохо обусловленных систем устойчивость этого метода оказывается недостаточной. Погрешность округления можно еще уменьшить, если выбирать в каждом цикле элемент а[А[[, и, [,-й, максимальный по модулю во всей матрице. Однако точность при этом возрастает не сильно по сравнению со случаем выбора главного элемента, а расчет заметно усложняется„ибо требуется перестановка не только строк, но и столбцов.
Этот способ невыгоден для ЭВМ и применяется только при расчетах с небольшим количеством знаков на клавишных машинах. Для контроля расчета полезно найти невязки: ТА=ЬА — 'У, 'аыхп 1~)с=-п. (7) бе1А =-+. П аЩ, (8) Если они велики, то это означает грубую ошибку в расчете (ошибка в программе, сбой ЭВМ). Если они малы, а система хорошо обусловлена, то решение найдено достаточно аккуратно. Правда, для плохо обусловленных систем малость невязок не гарантирует хорошей точности решения.
Метод Гаусса с выбором главного элемента надежен, прост и наиболее выгоден для линейных систем общего вида с плотно заполненной матрицей. Он требует примерно и' ячеек в оперативной памяти ЭВМ, так что на БЭСМ-4 можно решать системы до 60 порядка. При вычислениях производится '[,и' арифметических действий; из них половина сложений, половина умножений и и делений.
3. Определитель и обратная матрица легко вычисляются методом исключения. В самом деле, вычитание строки из строки не меняет значение определителя. Значит, в процессе исключения элементов (4) — (5) абсолютная величина определителя не меняется, а знак может измениться благодаря перестановке строк. Определитель же треугольной матрицы (6) равен произведению диагональных элементов, Поэтому он вычисляется по формуле: 1З1 линейные системы а и где знак зависит от того, четной или нечетной была суммарная перестановка строк.
Для вычисления определителя требуется примерно а' ячеек памяти и з1. л' арифметических действий. На примере вычисления определителя можно убедиться в экономичности хороших численных методов. Вспомним формальное определение определителя как суммы всевозможных произведений элементов, взятых из разных строк и столбцов. Таких произведений имеется п! — 1г 2пп (п1е)", и прямое их вычисление же при небольших и — 30 требует астрономического числа действий — более 0", что вряд ли когда-нибудь станет под силу ЭВМ.
Д метод исключения легко позволяет вычислять определители сотого и более порядка. Перейдем к вычислению обратной матрицы. Обозначим ее элементы через схг . Тогда соотношение АА-'=Е можно записать так: а У', агаааг=ба„1 = г, 1 =л. (9) а=! Видно, что если рассьратривать 1-й столбец обратной матрицы как вектор, то он является решением линейной системы (9) с матрицей А н специальной правой частью (в которой на 1-м месте стоит единица, а на остальных — нули).
Таким образом, для обращения матрицы надо решить п систем линейных уравнений с одинаковой матрицей А и разными правыми частями. Приведение матрицы А к треугольной по' формулам (4) — (5) делается при этом только один раз. В дальнейшем при помощи чисел с ь по формуле (5) преобразуются все правые части, и для каждой правой части делается обратный ход.
При хорошей организации вычислений для обращения матрицы этим методом требуется примерно 2п' ячеек оперативной памяти ЭВМ и 2а' арифметических действкй (можно уложиться в з/.из ячеек, но это сильно усложняет программу и увеличивает время счета), Заметим, что при обращении матриц контролировать расчет вычислением невязки Я=Š— АА-' невыгодно: перемножение матриц требует столько же действий (2из), как и обращение матрицы! Любопытно отметить, что обращение матрицы сводится к решению 'и систем линейных уравнений, а требует лишь втроебольше действий, чем решенйе одной системы уравнений.
Это объясняется тем, что при решении линейной системы ббльшая часть вычислений связана с приведением матрицы к треугольному виду, что при обращении матрицы делается только один раз. Обратный ход и преобразования правых частей выполняются много быстрее. Поэтому, если требуется несколько раз решить линейную систему с одной и той же матрицей, то выгодно привести матрицу к треугольной форме (6) только однажды, используя величины с ь во всех последующих вычислениях. СИСТЕМЫ УРАВНЕНИЙ )гл, ч 4. О другик прямых методах. Есть очень много других прямых методов решения задач линейной алгебры. Рассмотрим формальные харантеристики наиболее известных методов. Метод оптимального исключения имеет ту же скорость и требует той же памяти, что и метод Гаусса.
Но если матрица вводится в оперативную память ЭВМ не вся сразу, а построчно, то для метода Гаусса требуется '/зпа ячеек, а для метода оптимального исключения достаточно з/зпз ячеек. Практическая ценность эгого преимущества невелика, ибо построчный ввод овна ает много обращений к внешней памяти, т. е. сильное увеличение времени расчета. Кроме того, при построчном вводе невозможна выбрать главный элемент, что сказывае~ся на ошибках округленкя.
Метод окаймления мало отличается от метода оптимального исключения и имеет те же характеристики. Метод отражений требует вдвое большего числа действий, чем метод Гаусса (оператнвная память та же). Метод ортогоналнзации втрое медленнее метода Гаусса. Им интересовались в надежде на то, по он позволит решать плохо обусловленные системы. Но выяснилось, что прн бочьшнх и сама ортогоналнзация приводит к большой потере точности (сравните с разложением функции по неортогональным функциям), и лучше использовать методы регуляризации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
