III Канатников А.Н., Крищенко А.П. Аналитическая геометрия (3 изд. 2002) (1081381), страница 35
Текст из файла (страница 35)
Может ли неоднородная СЛАУ Ах = Ь быть неопределенной, если соответствующая однородная СЛАУ является определенной (неопределенной)? 2б9 Вопросы и палачи 9.6. Совместна или несовместна СЛАУ, если столбцы ее распоци иной матрицы линейно независимы (линейно зависимы)? 9.7. Может ли неоднородная СЛАУ Аж = Ь быть совмести ~й (несовместной), если соответствующая однородная СЛАУ и ил яется определенной (неопределенной)? 9.8. Привести примеры совместной и несовместной СЛАУ, ~ которых строки матрицы системы линейно зависимы.
Что м~окпо утверждать о совместности СЛАУ, если строки ее матрицы (расширенной матрицы) линейно независимы? 9.9. Квадратная СЛАУ Аж = Ь имеет невырожденную матрицу А, а свободные члены являются непрерывными функциями на отрезке (а, Ь]. Доказать, что любое решение этой СЛАУ «и:тоит из функций, непрерывных на этом отрезке. 9.10. Найти условие, при выполнении которого линейная аомбинация решений неоднородной СЛАУ будет: а) решением |той же СЛАУ; б) решением соответствующей однородной < 'ЛЛУ. 9.11.
Сколько решений может иметь неоднородная (одно~п~дная) СЛАУ, если столбцы ее матрицы линейно независимы? 9.12. Доказать, что неоднородная СЛАУ совместна, если ~ троки ее матрицы линейно независимы. 10. 'ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ 10.1. Проблемы, связанные с вычислениями При разработке любого численного метода решения какой- либо математической задачи возникает несколько общих проблем.
Первая проблема состоит в том, что теоретически корректный метод, приводящий к решению эа конечное число операций, может оказаться плохим или вообще неприемлемым, если это конечное число операций окажется слишком большим. Например, при решении СЛАУ с квадратной невыролсденной матриаей порядка и по правилу Крамера необходимо вычислить и+1 определитель и-го порядка.
При вычислении только одного из этих определителей „в лоб", согласно определению 7.1, требуется и!и — 1 арифметических операций. Таким образом, всего для решения системы требуется (а+1)(п!и — 1)+п операций. Уже при п = 23 это число имеет порядок 10з~. Даже при скорости 10э операций в секунду потребуется не менее 30000 лет! Вторая проблема связана с тем, что в практических задачах приходится иметь дело с неточными данными. При решении СЛАУ с квадратной матрицей требуется, чтобы определитель Ь матрицы системы был отличен от нуля.
Однако нарушение этого условия, т.е. соотношение Ь = О, никогда не выполняется точно, так как коэффициенгаы СЛАУ содержат, вообще говоря, погрешности, и определитель можно вычислить лишь приближенно. При этом, если определитель Ь мал по сравнению с коэффициентами системы, то небольшие погрешности могут приводить к существенному изменению решения. 271 10.1. Проблемы, связанные с вычислениями Пример 10.1. Рассмотрим системы < х+ у=1, х + 1,01у = 1,1. х+ у=1, х+ 1,01у = 1; и+1 = 1,1 Рис. 10.1 Говорят, что СЛАУ еелохо обусловлена, если незначиы льные изменения ее коэффициентов могут привести к существенному изменению ее решения. Если этого не происходит, ( ЛАУ называют хорошо обусловлееемоб. Третья проблема, возникающая в процессе вычислений, такло связана с погрешностями и вызвана тем, что вычисления при помощи компьютера или калькулятора выполняются лишь 1'~ шение первой них — х = 1, у = О, решение второй — х = — 9, у 1О.
Как видим, изменение всего лишь одного коэффициента ии !0% приводит к совсем другому результату. Понять при~ипу этого феномена проще всего с помощью геометрической ипчч рпретации СЛАУ. Данные системы можно рассматривать иик пары прямых на плоскости. Тогда их решения изображав|тел точками пересечения этих пар прямых. В нашем случае прямые „почти параллельны" (рис.
10.1). Поэтому незначительюп изменение положения одной из них приводит к большому ~ мщцению точки пересечения. 272 10. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ с конечным числом значащих цифр и потому их результаты содержат ошибки округлений (этого можно избежать только при вычислениях в целых числах, но диапазон целых чисел, используемых в компьютере, очень узкий, и это мажет привести к переполнению его разрядной сетки). В силу этой особенности, даже если все коэффициенты в СЛАУ заданы точно, решение получается, как правило, приближенным. 10.2.
Прямые и итерационные методы решения СЛАУ Мы остановимся на решении только таких СЛАУ, у которых матрица является квадратной и невырожденной. В этом случае система имеет решение, и притом единственное. Для его нахождения используются различные методы. Выбор метода решения СЛАУ определяет не только объем вычислений, но и точность получаемого этим методом результата. Прямые методы ретиенил СЛА У' выполняются за фиксированное число арифметических операций, не зависящее ни от значений коэффициентов, ни от требуемой точности вычислений (но зависящее, разумеется, от порядка системы). Если вычисления проводятся точно (например, в целых числах), то прямой метод всегда дает точное решение. Поэтому такие методы иногда называют тонными.
Пример точного метода (хотя и неприемлемого на практике для больших систем) — это правило Крамера. Лнзерационные мензоды решения СЛА У принципиально иные и априори строятся на том, что ответ в любом случае будет приближенным.
Каждый итерационный метод сводится к построению последовательности столбцов жр), ж(з1, ..., а(">, ..., которая в пределе дает решение СЛАУ. Каждый очередной столбец вычисляется на основе уже найденных и является более точным приближением искомого решения. Вычисление очередного столбца называют итерацией. В опре- 273 1Олп Метод Гаусса и си иный момент процесс прерывают, а последний полученный ~ омбец принимают за приближенное решение данной СЛАУ.
Как уже отмечалось, прямые методы решения СЛАУ выполииипся за фиксированное число шагов, зависящее для каждого икретного прямого метода лишь от размеров системы. Точи и ть получаемых при этом решений зависит как от свойств м~ тодов, так и от того, является СЛАУ хорошо обусловленной иии иет. В некоторых случаях прямые методы могут давать ~и ш рные результаты. Итерационные методы решения СЛАУ в сравнении с прямымн методами, как правило, более устойчивы к погрешностям вычислений.
Это связано с тем, что при использовании итерационных методов ошибки вычислений, содержащиеся в х~"~— !изультате и-й итерации, могут компенсироваться при вычи~н ини х("+0 — следующей, (и+1)-й итерации. Плохая обуловленность СЛАУ обычно приводит к тому, что замедляется яодимость последовательности х(") к решению системы и увеинчнвается число итераций для обеспечения нужной точности ~и шения.
10.3. Метод Гаусса Рассмотрим квадратную СЛАУ аых1+... + а1„х„= йы а 1х1+" Ч'а хи = ои с невырожденной матрипей А. Если в методе решения этой СЛАУ, изложенном в 9,7, зафиксировать определенный порядок преобразований (а любой ~исленный метод должен базироваться на точном порядке вычислений), то получится численный метод, известный как ляеюпод Гаусса исключения нензвестпных (или просто метпод Гаусса). Метод Гаусса имеет следующий алгоритм, состоящий 274 1П ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ иэ 2п — 1 шага. Запишем расширенную матрицу системы Ь1 Ьг Ьз ам агг а1з .. а1„ аг1 агг агз ° ..
аг„ (А ~ Ь) = аз1 азг азз ° .. аз аи1 аиг аьэ ° ° аии На первом шаге делим 1-ю строку расширенной матрицы на ее 1-й элемента11 и получаем новую строку (1,а,,а,..., а,„,Ь ). 1 1 1 11 Верхние индексы в коэффициентах а~ и Ь," указывают на то, что соответствующий элемент расширенной матрицы СЛАУ был пересчитан на й-м шаге метода Гаусса. Затем иэ каждой последующей 1-й строки вычитаем 1-ю, умноженную на коэффициент а;1.
В результате получаем матрицу аг аз Ь„' На втором шаге делим 2-ю строку на ее диагональный элемент агг и получаем новую 2-ю строку 10, 1, агз, ..., аг„, Ьг) расширенной матрицы. Затем из каждой последующей 1-й строки 11= 3,..., и) вычитаем полученную строку с коэффициентом а1 из 2-го столбца. В результате получаем матрицу О О а„..
а„„ а12 а1з 1 1 1 О агг а23 ° ° ° а2 1 1 1 О азг азз аз 1 1 1 1 а,г а1з ... а,„ 1 1 1 агз ". аг г О О азз ". аз 2 2 Ь' 1 Ьг Ьз Ь1 Ьгг Ьз 275 10.3. Метод Гаусса Процесс продолжаем до последней строки расширенной матрицы. На п-м шаге остается разделить последнюю строку ни !и диагональный элемент а„"„', и мы получим матрицу агг а1з 1 1 1 агз " аг. г О О 1 ... азз Ь! 1 Ьг Ьз О О О ... 1 Ьи+1 1 Ь +1 г Ь"+1 з агг агз 1 1 1 г агз .. аг„, О а3„ О 1 О О О О О ... 1 О О О О ... О 1 Ь"+' и-1 Па (и+2)-м шаге вычитаем (и — 1)-ю строку из всех предшетпующих с коэффициентами из (и — 1)-го столбца. Получаем В результате выполненных преобразований приходим к ! 'ЛЛУ, эквивалентной исходной.
Маунрииа этой СЛАУ являет- ~ г нерзне!1 треугольной и имеет диагональные элементы, равнин единице. На этом завершается первая часть алгоритма м! тода Гаусса, которую называют тгрягиьела аодоле метаода ! 'пусса. Вторая часть алгоритма состоит в преобразовании верхний треугольной матрицы в единичную, эту часть называют !!братаным аодола лаетаода Гаусса. Итак, продолжаем прес!разования. На 1и+1)-м шаге (первый шаг обратного хода) вычитаем и и леднюю строку из всех предшествующих с коэффициентами цз и,-го столбца.
Получаем матрицу 276 20. ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ матрицу 1 агз а,з ... а,„2 0 0 ! ! ! 0 1 азз .. а2„2 0 0 0 0 1 ° ° ° а3~ 2 0 0 1 0 0 0 0 0 0 1 0 0 0 1 Процесс продолжаем до 2-й строки. На последнем (2п — 1)-м шаге вычтем из 1-й строки 2-ю с соответствующим козффици ентом а!!2 и в результате получим расширенную матрицу видя (Е(ь'), где Ь!=(62"-! 62"-2 .. Ь"+! Ь") г ". -! ° ) столбец, представляющий собой искомое решение. Последовательные шаги алгоритма могут быть сведены к сеРии фоРмУл 1в них ае = аеб 6е = Ь;): ° прямой ход 2-й шаг, ! = 1,...,п — 1: 61-! !-! ' 3$ Ь) а~я, —— а~я, .
! — а~; ! а;' у'= 2+1,...,п, 6=2+1,...,п; Ь~, — — Ь~ ! — ал~; Ь;', — п-й шаг: Ьа Ьи и-!' а„,, фй, х„= 6„; 0 0 0 0 0 0 а,, в-! и Ьи+2 ! ь",+' ь"+' з Ьп+1 и — 1 Ь"+' и-! 22~ !Оса Особенности метода Гаусса ° об!ратный ход — !тй шаг, ! = и+1,...,2п — 1: х,=б; — ~ а, 'х, !=в+1 И приведенных формулах представление процесса вычислеиии как преобразования расширенной матрицы системы тени!тсн. Двойной нижний индекс в буквенных обозначениях и!а !ает, что в процессе вычислений необходимо использовать !иум! рный массив. Верхний индекс отражает лишь шаг проши ! а вычисления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
