Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 25
Текст из файла (страница 25)
Первое из этих свойств имеет простой геометрический смысл, именно, градиент $ есть проекция вектора и = АХ (градиента (АХ. Х) ) на подпространство, ортогональное к вектору Х, ибо т1 = и(Х) Х+1, причем р(Х) Х пропорционально Х и $ ортогонзльно к Х. Это обстоятельство легко можно было бы обосновать посредством чисто геометрического рассмотрения, без использования проведенных выше вычислений, но мы на этом не будем останавливаться. ГЛАВА 11 ТОЧНЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ Настоящая глава посвящена трем задачам, тесно связанным друг с другом: задаче решения линейной неоднородной алгебраической системы уравнений, задаче обращения матрицы и так называемой задаче исключения.
Все эти задачи теоретически решаются достаточно просто. Однако при большом порядке матрицы, связанной с задачеи, фактическое решение этих задач требует большого числа вычислительных операций. В настоящее время имеется большое количество методов численного решения систем линейных уравнений, и работа над их усовершенствованием интенсивно ведется в наши дни. Численные методы, решающие указанные задачи, делятся на две группы: точные и итерационные методы. Под т о ч и ы м и м е т о д а и и мы подразумеваем методы, которые дают решение задачи при помощи конечного числа элементарных арифметических операций.
Прн этом, если исходные данные, определяющие задачу, заданы точно (например, если они целые или рациональные числа, представленные в виде обыкновенных дробей) и вычисления выполняются точно (например, по правилам действий над обыкновенными дробями), то решение также получается точное. В точных методах число необходимых для решения задачи вычислительных операций зависит только от вида вычислительной схемы и от порядка матрицы, определяющей данную задачу.
Исторически первым методом этой группы является метод, основанный на идее исключения неизвестных. В применении к решению линейной неоднородной системы алгорифм этого метода, связанный с именем Гаусса, состоит из цепочки последовательных исключений, посредством которых данная система превращается в систему с треугольной матрицей, решение которой не составляет труда. В настоящее время разработано много различных вычислительных схем метода Гаусса в применении ко всем трем упомянутым задачам.
Среди этих схем следует отметить так называемые компактные схемы, требующие минимальной записи или запоминания промежуточных результатов. В компактных схемах используется операция накоплениЯ, т. е, вычислениЯ сУмм вида ~~'„авбв, ПРименение этой 138 точныи мвтоды ввшвния систем линвйных гвлвнений 1гл. и операции с двойной точностью, т. е. с сохранением всех значащих цифр отдельных слагаемых с округлением лишь после окончания суммирования, аначительно снижает ошибки округления. Близким к методу Гаусса является метод, основанный на идее окаймления. В основе этого метода лежит представление данной матрицы в виде последовательно вложенных друг в друга матриц, начинзя с матрицы первого порядка.
Различные модификации метода исключения, так же как и метод окаймления, по существу связаны с разложением матрицы в произведение двух треугольных матриц, теоретически описанным в й' 1, п. 12. К точным методам обращения матриц относится и метод, основанный на идее постепенного изменения обращаемой матрицы с внесением последовательно поправок к обратной (метод пополнения). В последние годы получили большое распространение точные методы, основанные на идее построения вспомогательной системы векторов, ортогональных в той или иной метрике. Как будет показано ниже, метод Гаусса может быть включен и в эту группу методов. Итерационные методы доставляют средство для приближенного решения системы линейных уравнений. Решение системы при помощи итерационных методов получается как предел последовательных приближений, вычисляемых некоторым единообразным процессом. При применении итерационных методов существенным является не только сходимость построенных последовательных приближений, но и быстрота сходнмости.
В этом отношении каждый итерационный метод не является универсальным; давая быструю сходимость для одних матриц, он может сходиться медленно нли даже совсем не сходиться для других матриц. Поэтому прн применении итерационных методов важную роль играет предварительная подготовка системы, т. е. замена данной системы ей эквивалентной, устроенной так, чтобы для нее выбранный процесс сходился по воаможности быстро, а такх<е различные приемы ускорения.
Настоящая глава книги посвящена изложению простейших методов, входящих в группу точных методов. другие методы (точные и итерационные) будут излагаться далее на протяжении почти всей книги. й 15. Обусловленность матриц При численном решении систем линейных уравнений даже точными методами возникает несколько источников неточности решения. Одним из них является необходимость округления чисел в процессе вычисления. При этом может случиться, что по ходу вычисления придется столкнуться с явлением исчезновения значащих цифр в результате вычитания двух величин, близких друг другу. Исчезновение значащих цифр может быть причиной настолько значительного снижения точности результата, что из-за этого иногда бывает необходимо изменить схему вычисления или переделать работу с ббльшим числом значащих цифр в промежуточных выкладках, 139 9 15] овьсловлзнность млтгиц 6 5 7 10 8 7 8 7 1О 9 9 10 Нетрудно вычислить, что ~ Ф') = 1. При этом — 41 — 17 10 25 10 — 6 68 — 41 10 5 — 3 — 6 — 3 2 — !7 10 Второй источник появляется в условиях, когда система линейных уравнений возникает в процессе решения практической задачи, так что элементы матрицы коэффициентов, так же как и свободные члены, известны лишь и р и б л н ж е н н о, с некоторой степенью точности.
Неточность самих исходных данных порождает ошибки в решении, так как изменение коэффициентов системы в пределах заданной точности влечет за собой изменение решения. Займемся более детально исследованием этой причины неточности в решении системы. Теоретическое решение системы АХ= Г дается формулой Х=-А 'тч, где А ' матрица, обратная к А. Как известно, А ' существует в том и только в том случае, если ! А ! + О.
Однако, если элементы матрицы А заданы приближенно, возможно, что даже сам вопрос о том, имеет ли матрица А отличный от нуля определитель или нет, лишен смысла. Именно, может случиться, что ири точном вычислении определителя, исходя из приближенных значений элементов матрицы, принятых за точные, определитель оказывается отличным от нуля, но изменение элементов в пределах точности их задания может привести к матрице с нулевым определителем. Ясно, что система с матрицей, обладающей указанным свойством, не может быть решена со сколько-нибудь удовлетворительной точностью. Система практически оказывается несовместной. Мы будем называть обратную матрицу у с т о и ч и в о и, если малым иаменениям в элементах матрицы будут соответствовать малые изменения в элементах обратной матрицы. Очевидно, что для устойчивости обратной матрицы во всяком случае необходимо, чтобы определитель матрицы был бы не слишком мал. Степень малости определителя, препятствующую получению устойчивой обратной матрицы, трудно определить раз навсегда, ибо само понятие „не слишком мал" вряд ли может быть определено точно.
Прежде чем переходить к уточнению этого понятия, рассмотрим следующий пример. Пусть 140 точныв методы гашения систем лиивйных гвлвнвний [гл, и Если считать, что элементы матрицы 1Р' заданы абсолютно точно, то все обстоит благополучно. Однако определитель матрицы является довольно малым. В самом деле, известная оценка Адамара для значения определителя дает (%' ! ( "у' 2 534 437 350 ~ 50 000, что означает (в силу достижимости оценки Адамара), что прн таких же суммах квадратов модулей элементов строк модуль определителя может доходить до 50000. Это дает основание предположить, что матрица Уг' ' будет мало- устойчивой, что легко подтверждается следующим рассуждением, Проследим, как изменяется определитель матрицы Ю' при малых изменениях ее первого элемеята.
Пусть 5+з 7 6 5 7 10 8 7 1г'(е) = 6 8 1О 9 5 7 9 10 Тогда (К(а))=1+68е, откуда следует, что приз= — —.. — 0.015 1 68' матрица В'(е) будет особенной. Таким образом, если считать элементы матрицы 1Р' известными с точностью до 0.02, то практически матрица В' должна рассматриваться как особенная. Покажем, как будут меняться все элементы обратной матрицы при незначительном изменении первого элемента матрицы В'.
Пусть 5.0002 7 6 5 7 1О 8 7 6 8 10 9 5 7 9 10 Тогда ~ В', ( = 1.0! 36, 67.088 — 40.450 — 16.772 9.866 — 40.450 24.664 9.862 — 5.916 — 16.772, 9.862 4.943 — 2.966 9. 866 — 5. 916 — 2. 966 1. 980 э 15! ! 4! овхсловленность млтвнц и, следовательно, 0.9!2 — 0.550 — 0.228 0.134 — 0.550 0.335 О.!38 — 0.084 — 0.228 0.138 0.057 — О.ОЗЗ 0.134 — 0.084 — 0.033 0.020 Еще большее расхождение мы получим, если рассмотрим матрицу 499 7 6 5 10 8 7 6 8 1О 9 5 7 9 10 для которой (Ю' ~ =0.320, н 204.82 — 128.12 — 53.12 31.25 — 128.12 — 53.12 77.53 31.78 — 18.81 31.78 14.03 — 8.31 '31.25 — 18.81 — 8.31 5.12 АА '=Е имеем — А +А — =О, дА -~ дА да0 дэ0 откуда д(А ') — А т дА А д В дав Но Интересно отметить, что при этом само определение элементов матриц В' , %'~ и Ф', не встречает трудностей, связанных, например, с исчезновением значащих цифр. Выясним теперь в общем виде, как могут изменяться элементы обратной матрицы при изменениях элементов самой матрицы.
Пусть А '=!а, ). Иэ равенства 142 точныв методы вешания систвм линейных ввавнвний [гл, и где еб матрица, элемент 1-й строки и 1-го столбца которой равен единице, все остальные элементы равны нулю. Следовательно, д(А ') -= — А е;А = — А ене;А даг. ат ауз . ° . ауа О 0 ... 0 О ... 0 аы а.; 0 ... 0 агл0...0 0 0 ... 0 апауг ана, ... амата аывдг аыа в аыа -„ аасяуг аа'а12 ' ' ' аюпов и потом)' д2 | — авРд. даг откуда данная система. Тогда Х.= А 'Г и, следовательно, анхд аых г — г. = — А е "А га.= — А еуХ=— дХ дА дага дав. О.
г Таким образом, изменение каждого элемента обратной матрицы. вызванное изменением элемента аы, равно этому изменению, умноженнсму на произведение некоторых двух элементов обратной матрицы. Если элементы обратной матрицы достаточно велики (что при малом определителе бывает всякий раз), то незначительная ошибка в элементах исходной матрицы влечет за собой значительные изменения в элементах обратной, Нонечно, в некоторых случаях ошибки от изменения различных элементов матрицы могут компенсировать друг друга. Будем называть матрицу плохо обусловленной, если соответствуюшзя ей обратная матрица будет неустойчивой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
