Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 3
Текст из файла (страница 3)
В многочисленных практических ситуациях воэникаюг матричные задачи, хотя и несимметричные, но имеющие симметричную структуру; при этом можно показать, что применение к ним гауссова исключения не требует выбора главных элементов для обеспечения численной устойчивости. Почти все идеи и алгоритмы, описываемые в книге, непосредственно приложимы к этому классу задач.
Некоторые указания на то, как это можно сделать, даны в упр. 4.5.1 главы 4. й 1.3. Итерационные и прямые методы Численные методы для решения систем линейных уравнений распадаются на два больших класса; итерадионные и прямые. Типичный итерационный метод состоит из выбора начального В П8. Итерационные и прямые методы !9 приближения хго к х и построения последовательности х<'>, х!е!, ..., такой, что !!гп ха!=х. Обычно для вычислении х!'+'> ! .+ нужны лишь А, 6 и одно или два предыдущих приближения. В теории при использовании итерационного метода мы должны выполнить бесконечное число арифметических операций, чтобы получить х, но на практике мы прекращаем итерацию, когда, с нашей точки зрения, очередное приближение достаточно близко к х С другой стороны, при отсутствии ошибок округления прямые методы позволяют вычислить решение за конечное число арифметических операций.
Какой класс методов лучше? На этот вопрос нельзя ответить безусловно; ответ зависит от того, какой смысл мы вкладываем в слово «лучше», а также от конкретной решаемой задачи или класса задач. Итерационные методы привлекательны с точки зрения требований к машинной памяти, поскольку их реализация в типичном случае требует хранения лишь А, Ь, хш и еше, может быть, одного или двух векторов. В то же время при разложении матрицы А она обычно претерпевает некоторое заполнение, так что матраца заполнения') Г = х + е.г имеет ненулевые элементы в тех позициях, где в А стояли нули. Поэтому реализация прямых методов часто требует большей памяти, чем реализация итерационных. Реальное отношение очень сильно зависит от решаемой задачи и от используемого упорядочения.
Сравнение прямых и итерационных методов с точки зрения вычислительной работы еще более затруднено. Как мы видели, выбор упорядочения в огромной степени влияет на количество арифметической работы при использовании гауссова исключения. Число итераций, выполняемых итерационной схемой, сильно зависит от характеристик А и от подчас деликатной проблемы регистрации, посредством вычисляемых величин, момента, когда ха! «достаточно близок» к х.
В некоторых ситуациях, например, при конструировании некоего механического устройства или моделировании какого-нибудь разворачивающегося во времени явления приходится решать много систем уравнений с одной н той же матрицей коэффициентов. В этом случае стоимость прямой схемы может по существу совпадать со стоимостью решения треугольной системы при известнож разложении, поскольку стоимостью единственного разложения, отнесенного ко всем системам, можно пренебречь В этих ситуациях часто верно и то, что чйсло ите!раций, требуемых итерационной схемой, очень невелико„ по. скольку имеются хорошие начальные векторы ха>, После этих замечаний должно быть ясно, что пока вопрос о том, какой класс методов следует использовать, не поставлен ') В оригинале — !пе И!ед гпа!Пх — Прим. верее.
20 Гл ! Введение в очень узком и хорошо определенном контексте, ответ на него или слишком сложен или вообще невозможен. Причина, почему в этой книге рассматриваются лишь прямые методы, та, что по итерационным методам уже имеется несколько отличных справочных книг (Чагина 1962, Уонип 1971); в то же время авторам не известна сравнимая книга по прямым методам для больших разреженных систем. Вдобавок существуют ситуации, когда можно очень убедительно показать, что прямые методы намного предпочтительней, чем любая мыслимая итерационная схема.
2, Вводные сведения й 2.0. Введение В этой главе мы исследуем основной численный алгоритм, используемый во всей книге для решения симметричных положительно определенных матричных задач. Этот метод, известный как метод Холесского, кратко обсуждался в $ !.1 Ниже мы докажем, что для положительно определенных матриц разложение всегда существует, и изучим несколько способов, которыми могут быть организованы вычисления Хотя математически и (обычно) численно эти способы эквивалентны, они различаются порядком, в котором вычисляются и используются коэффициенты. Эти различия важны при машинной реализации метода. Будут выведены также выражения для числа арифметических операций, требуемых методом.
Как было указано в 5 1.1, при применении метода Холесского к разреженной матрице А она обычно претерпевает некоторое заполнение, так что множитель Холесского ь имеет ненулевые элементы в позициях, где в А стояли нули. При некоторой матрице перестановки Р мы можем вместо А разложить в произведение Ыг матрицу РАР', и в соответствии с тем илн иным критерием Е может оказаться много привлекательнее, чем Е В $ 2,3 мы обсуждаем некоторые из этих критериев и показываем, как факторы, обусловленные практической реалнзацией, усложняют сравнение различных методов. 2.0А. Обозначения Предполагается, что читатель знаком с элементарной теорией и свойствами матриц; см., например, т3(еваг1 1973). В этом параграфе мы опишем матричные обозначения, используемые в книге.
Для обозначения матриц использую1ся жирный курсив и прописные буквы. Элементы матрицы обозначаются курсивными строчными буквами с двумя индексами. Например, пусть А — Мр',Ф-матрица, Ее элемент (й 1) обозначается через ан. Число М называется порядком матрицы А. 22 Гл а впаднне сведения Вектор обозначается жирной строчной буквой, а его компоненты — строчными буквами с одним индексом. НапримеР, Уз — вектор длины М.
Для данной матрицы А ее (-я строка н (-й столбец обозначаются через А,„и А„соответственно. Если А симметрична, то Аы = А., для 1 = 1, ..., М. Для единичной матрицы порядка М, т. е. для матрицы, у которой на диагонали стоят единицы, а вне диагонали — нули, используется обозначение 1и. В анализе разреженных матриц часто приходится подсчитывать число ненулевых элементов вектора или матрицы.
Мы пользуемся символом ~)(12) для числа ненулевых коэффициентов в гз, где символ с1 замещает название вектора или матрицы. Очеви но г1(т ) =и' Часто приходится упоминать о числе элементов в множестве 5; это число обозначается через 15(. Пусть )'(п) и й(л) — функции независимого переменного л.
Будем писать 1(л) = 0(д(п)), если для некоторой константы К н всех достаточно больших л Мы скажем, что )(п) есть, самое большее, величина порядка д(л). Это полезное обозначение в анализе разреженных матричных алгоритмов, поскольку часто интерес представляют лишь доминирующие члены в оценках арифметики и количества ненулевых элементов. 1 з 1 т 2 Например, если 1 (л) = — п + — п — — и, то можно написать О( з) Для достаточно больших и относительный вклад членов — л 1 2 2 и ( — — и) несуществен. 3 Выражения типа выписанной выше )(и) возникают при подсчете числа арифметических операций или количества ненуле- б 2.1.
Алгоритм разложения 23 вых элементов и являются часто результатом довольно сложных суммирований. Поскольку обычно мы интересуемся лишь главным членом, то очень распространенный прием упрощения таких подсчетов состоит в замене знака суммы на символ интеграла. Например, для больших п л з (2п+ Й)(п — Й) ~ (2н+ й)(п — й) йй. «-! з 1)пражнения н 2,0.), Вычислить непосредственно сумму ~ р(в' — !), а затем найти ее приближенное значение, используя интеграл, как указано в конце параграфа.
2.0.2. Вычислить непосредственно сумму и н-гч! (!'+ 1), а затем с помощью двойного интеграла приближенное значение. 2.0.3. Пусть А и  — разреженные матрицы порялка )у. Показать, что число умножений, необходимых при вычислении С =- АВ'), равно и ~„Ч (А,!) Ч (Вы). ! ! 2.0А. Пусть  — разреягеиная М Х Н-матрица. Показать, что для вычисления В"В достаточно умножений. 2.0.5. Обычная схема хранения разреженного вектора такова имеются основной массив, содержащий значения всех ненулевых компонент вектора, и вспомогательный массив, хранящий индексы этих компонент. Пусть и н ив два разреженных вектора порядка Л), хранимых таким образом Рассмотреть задачу вычисления скалярного произведения ю =- и"о.
а) Есчи индексные векторы упорядочены по возрастанию (или убыванию), показать, что для вычисления скалярного произведения достаточно вы. полнить О(ч(м) + ч(о)) сравнений б) А если индексы размещены случайным образом> в) Как бы вы организовали вычисления, если бы индексы были размещены случайно, но у вас в распоряжении находился рабочий вещественный массив длины Н с нулевыми компонентами) В 2.1. Алгоритм разложения 2.1,1. Существование и единственность разложения Симметричная матрица А называется положительно определенной, если х"Ах ) О для всех ненулевых векторов х. Такие ') В соответствии с определением произведения матриц — Прим перев. я4 гл.
2. Вводные сведения матрицы появляются во многих пРиложениЯх; в типичном слУ- тл» представляет энергию иекотор й физиорая положительна для любой конфигурации х, Б положительно определенной матрице А диагональные элементы всегда положительны, поскольку е Ае=атр т где е — т-й характеристический вектор, все компоненты которого равны нулю, кроме 1-й, равной единице. Это обстоятельство будет использовано в доказательстве следующей теоремы о разложении, принадлежащей Холесскому (Б1еиаг1 1973).
Теорема 2.!.!. Если А — М;»', М симметричная положительно определенная матрица, то существует и единственно ее треугольное разложение Е1.т, где Т вЂ” нижняя треугольная матрица с положительными диагональными элементами. где д — положительный скаляр, а Й вЂ” матрица порядка тч' — 1. Блочную матрицу можно записать как произведение ,э- „тт у 1 О т ,д. Тп -1 О Н О эьт Здесь Н=Н вЂ” хи —. Ясно, что матрица Н симметрична.
Она в будет и положительно определена, потому что для любого ненулевого вектора х порядка Ф вЂ” 1 х т „т т1 =х ~Й- — ~х =х Нх, Доказательство. Будем проводить доказательство индукцией по порядку матрицы А. Очевидно, что утверждение справедливо для матриц порядка 1, так как ац — положительное число. Предположим, что утверждение верно для матриц порядка М вЂ” 1. Пусть А — симметричная положительно определенная матрица порядка М. Ее можно представить в блочной форме 5 дт Алгоритм риэлоягения лб откуда следует «тН» ) О. По предположению индукции, Н имеет т треугольное разложение Енйн, причем диагональ 2.н положительна.
Поэтому А может быть разложена з произведение ги „т)э тл 1 0 У гн-1 ч/К Е Ет я-и гп те э~ Е 1.й =Ы,т г-и чга Применяя результат теоремы к матрице 8 25 получим множители Здесь уместно отметить, что сушествует другое разложение симметричной положительно определенной матрицы, тесно связанное с рассмотренным (МагВп 1971), Поскольку множитель Холесского имеет положительные диагональные элементы, то можно вычленить из Е диагональную матрицу 0иэ, что дает Ь = 2.2У"э я А = Х)лЕ~, В рассмотренном выше примере это (2.!.1) разложение таково: Такое разложение столь же легко получить, как и первоначальное, н при этом не потребуется извлекать квадратные корни (см. упр. 2!А). Мы не используем его а этой книге, потому что при некоторых обстоятельствах оно приводит к неприятной асимметрии в вычислениях с блочными матрицами 2.!.2. Вычисление разложения Теорема 2.1.1 гарантирует сушествование и единственность множителя Холесского для симметричной положительно определенной магрицы, однако порядок и способ реального вычисле.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
