Турчак Л.И. Основы численных методов. Под ред. В.В.Щенникова (1987) (1095857), страница 20
Текст из файла (страница 20)
Объем вычислений заранее определить трудно. Тем не менее итерационные методы в ряде случаев предпочтительнее. Они требуют хранения в памяти машины не всей матрицы системы, а лишь нескольких векторов с п компонентами. Иногда элементы матрицы можно совсем не хранить, а вычислять пх по мере необходимости. Погрешности окончательных результатов прп использовании итерационных методов не накапливаются, поскольку точность вычислений в каждой итерации определяется лишь результатами предыдущей итерация и практически не зависит от ранее выполненных вычислений. Эти достоинства итерационных методов делают их особенно полезными в случае большого числа уравнений, а также плохо обусловленных систем.
Следует отметить, что при этом сходимость итераций может быть очень медленной; поэтому ищутся эффективные пути ее ускорения. Итерационные методы могут использоваться для уточнения решений, полученных с помощью прямых методов. Такие смешанные алгоритмы обычно довольно эффективны, особенно для плохо обусловленных систем, В последнем случае могут также применяться методы регуляризацпи, у ь основнын понятия 3. Другие задачи линейной алгебры. Кроме решения систем линейных уравнений1 существуют другие задачи линейной алгебры — вычисление определителя, обратной матрицы, собственных значений матрицы и др. Легко вычисляются лишь определители невысоких порядков п некоторые специальные типы определителей.
В частности, для определителей второго и третьего порядков соответственно имеем ! 11 12 = 1111а22 1121п12 21 22 аз 21 22 23 аЗ а32 '33 П11П22ПЗЗ + 1112~231131 + 1121П32П13 1131122Р13 п2Р121233 12321223а11' Определитель треугольной матрицы равен пропзведенпю ее элементов, расположенных на главной диагонали: Р = а„а22...а„„. Отсюда также следует, что определитель единичной матрицы равен единице, а нулевой — нулю: йе$ Е = 1, йе10 = О. В общем случае вычисление определителя оказывается значительно более трудоемким. Определитель Р порядка и имеет вид (4.4) Р =,~~( — 1) а1аа26... а„о~' Ъ Из этого выражения следует, что определитель равен сумме п1 слагаемых, каждое из которых является произведением и элементов.
Поэтому для вычисления определителя порядка и 1без использования специальных приемов) требуется (и — 1) п! умноя."ений и и! — 1 сложений, т. е. общее число арифметических операций равно Ж-и п1 — 1=п п1. (4.9) Оценим значения У в зависимости от порядка и определителя: З 10 17 3.6 10' 5 1013 Мон'но подсчитать время вычисления таких определителей на ЭВМ с заданным быстродействием. Примем для определенности среднее быстродействие равным 100000 операций в секунду.
Тогда для вычисления определителя 10-го порядка потребуется около 6 млн, а прп и = 20— около 1.4 10" ч, т. е, свыше 5 10' сут. Приведенные гл 4. спстезп1 лпппйт1ьтх уРлвпеп11Й оценки указывают па необходимость разработки и использования экономичных численных методов, позволяюгцих эффективно проводить вычисления определителей. В ~ 2 будет рассмотрен один из таких методов. Матрица А ' называется обратной по отношевппо к квадратной матрице А, если пх произведение равно единггчной матрице: ЛА '=А 'А =Е.
В линейной алгебре доказывается, что всякая невырождеппая матрица А (т. е. с отличным от пуля определителем УУ) имеет обратную. При эхом с1е1 А ' = 1/УУ. Запишем исходную матрицу в виде . а ... аг ... аг А= аи ...ап а1 '' аг ''' 7777 Минорои элемента а77 называется определитель гг —- — 1-го порядка, образованный из определителя матрицы А зачеркиванием г-й строки и у-го столбца. Алеебраическии догголнениев Ао элемента а77 называется его минор, взятый со знаком плюс, если сумма г+у номеров строки г и столбца у четная, и со знаком ъпгнус, если эта сумма нечетная, т.
е. 1,у — 1 1,г 4-1 а11 1)7+2 1-1,1 ' ' ' 7-1а — 1 7'-1,2+1 ' ' 7 — 1,л и ... а. а.... а. 7У = 7+1,1 ' ' ' 7+1А — 1 1+1 У+1 ' ' ' 7+1,77 а1 '' а У вЂ” 1 а3 )1 ''' 77а А й А А„ О А„ /~ 22 А, В А'= А„в ° ° ~ р 177 2 77 Каждый элемент Уг„(г,у = 1, ..., гг) обратной матрицы В = А ' равен отношению алгебраического дополнения Ав элемента а,7 (не а7„.) исходной матрицы А к значению ев определителя Ху: 121 5 2, пРямые мктолы Здесь, как и выше, можно также подсп1тать число операций, необходимое для вычисления обратной матрицы без использования специальных методов.
Это число равно сумме числа операций, с помощью которых вычисляются и'- алгебраических дополнений, каждое из ко- $ торых является определителем и — 1-го порядка, п и- делений алгебраических дополнений на определитель В. Таким образом, общее число операций для вычислений обратной матрицы равно У = ~ (и — 1) (п — 1) 1 — 11и' + ~г'+ и п1 — 1 = и' и ~ — 1, (4 11) Важной задачей линейной алгебры является также вычисление собственных значений матрицы.
Этому вопросу будет посвящен отдельный параграф. 5 2. Прямые методы 1. Вводные замечания. Одним из способов решения системы линейных уравнений является правило Крамера, согласно которому каждое неизвестное представляется в виде отношения определителей. Запишем его для системы ах+ оу с„ 02х+ б,д = сь Тогда х=оЮ, у ВЮ, 0 0 Б Можно попытаться использовать это правило для решения систем уравнении произвольного порядка. Однако при большом числе уравнений потребуется выполнить огромное число арифметических операций, поскольку для вычислений и неизвестных необходимо найти значения определителей, число которых и+1.
Количество арифметических операций можно оценить с учетом формулы (4.9). При этом предполагаем, что определители вычисляются непосредственно — без использования экономичных методов. Тогда получим Х = (и+ 1) (и и! — 1) + и. Поэтому правило крамера можно использовать лишь для решения систем, состоящих из нескольких уравнений, гл. 4. системы линейных уРАВнений а„х, + а„х, + а„х, = Ь„ а21Х1 + а22Х2 + а ~зхз ЬЗ аз!Х1 + аз2Х2 + аззХз ~з' (4.12)' Для исключения х, пз второго уравнения прибавим к нему первое, умноженное на — а„/а„.
Затем, умножив первое уравнение на — а„/а„и прибавив результат к третье- Известен также метод решения линейной системы о использованием обратной матрицы. Спстема записывается в виде АХ =В (см. (4.3)). Тогда, умножая обе частп этого векторного уравнения слева на обратную матрицу А ', получаем Х = А 'В. Однако если пе использовать экономнчных схем для вычпсленпя обратной матрицы, этот способ также непригоден для практпческого решенпя линейных систем при больших зпаченнях и пз-за большого объема вычислеипй. Наиболее распространенными средн прямых методов являются метод исключения Гаусса и его модификация.
Ниже рассматривается прнменеппе метода исключения для решения систем линейных уравнений, а также для вычисления определителя и нахождения ооратной матрицы. 2. Метод Гаусса. Он основан на приведенпп матрицы системы к треугольному виду. Это достигается последовательным исключением непзвестных нз уравнений системы. Сначала с помощью первого уравнения исключается х, пз всех последующих уравнений системы. Затем с помощью второго уравненпя исключается х, нз третьего и всех последующих уравнений. Этот процесс, называемый прял~ым ходом лзетода 1'аусса, продолжается до тех пор, пока в левой части последнего (п-го) уравнения не останется лишь один член с неизвестным х„, т.
е. матрица системы будет приведена к треугольному виду. (Заметим, что к такому виду приводится лишь невырожденная матрица. В противном случае метод Гаусса пеприменпм.) Обратный ход метода Гаусса состоит в последовательном вычисленпи искомых неизвестных: решая последнее уравнение, находим единственное неизвестное х„. Далее, используя это значение, из предыдущего уравнения вычисляем х„1 и т. д. Последним. найдем х, пз первого уравнения. Рассмотрим применение метода Гаусса для системы я 2.
пРямые методы му уравнению, также исключим иа него х~. Получим равносильную систему уравнений вида а„х, + а1зхз + а„х, = Ь„ 1 / Р аз,х + а,зхз —— Ьз,- Р Р Р аззхз + аззхз = Ьз~ (4.13) а,. а;; = а;; — — ' а1/, г, у = 2, 3,. 11 а,. Ь, = Ь,— — *Ь„ "11 ~ = 2, 3, Теперь из третьего уравнения системы (4.13) нужно исключить х,.
Для этого умножим второе уравнение на Р / Р— азз,/'а,з и прибавим результат к третьему. Получим а„х, + а1 зхз + а1зха = Ь1. / Р / аззхз + аззхз — Ь„ У! 33 аззхз = Ьз~ / азз Ьз Ьз Ьз 22 (4 14) Используя это значение, можно найти х, из второго уравнения, а затеи х, иэ первого: 1 1 хз = —, ~Ьз — азах,), х, = — (Ь, — а,зхз а1зхз) азз 11 Аналогично строится вычислительный алгоритм для линейной системы с произвольным числом уравнений. Матрица системы (414) имеет треугольный вид. На этом заканчивается прямой ход метода Гаусса. Заметим, что в процессе исключения неизвестных приходится выполнять операции деления на коэффициенты а„, а„и т. д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
