Учебник - Практические занятия по вычислительной математике - Аристова (1238839), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Рассматриваются простейшие прямые и итерационныеметоды решения СЛАУ. К численному решению систем линейных алгебраических уравнений сводятся многие задачи математической физики.Математические модели, представляющие собой СЛАУ большой размерности, встречаются в математической экономике, биологии и т. п.К другим методам линейной алгебры мы вернемся при рассмотренииметодов решения сеточных уравнений, возникающих при аппроксимацииразностными методами дифференциальных уравнений в частных производных эллиптического типа.По прикладной линейной алгебре существует обширная литература,например, [11–15]. Программы, реализующие популярные алгоритмы вычислительной линейной алгебры, являются неотъемлемой частью прикладного программного обеспечения, в частности, современных математических пакетов.II.2.

Некоторые сведения о векторных пространствахНорма. Будем ставить в соответствие каждому элементу n-мерноговекторного пространства A неотрицательное число m(A), называемоенормой. Оно должно удовлетворять следующим трем свойствам (аксиомам нормы).1. m(A)  0  A  0.Если первая аксиома не выполняется и ноль может соответствовать иненулевому элементу, то это число – полунорма.2. Для любого скалярного множителя α выполнено m(αA) = |α|m(A).33II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫ3.

m(A + B) ≤ m(A) + m(B) (неравенство треугольника).Ниже мы увидим, что норму в векторном пространстве можно задатьнеединственным способом.II.2.1. Согласованные и подчиненные нормы векторов и матрицВ векторном n-мерном линейном нормированном пространстве введем следующие нормы вектора:кубическая: || u ||1  max | ui |,(2.1а)1 i  nnu 2   ui ,октаэдрическая:(2.1б)i 1евклидова (в комплексном случае – эрмитова):121 n2u 3    ui   (u,u) 2 .(2.1в) i 1Такое обозначение соответствует традициям научных школ, сформировавшихся в МФТИ.

Такие обозначения приняты ниже во всех задачах.Рассмотрим квадратную матрицу А и связанное с ней линейное преобразование v = Au где v, u  RN (RN – N-мерное линейное нормированноепространство). Норма матрицы определяется как действительное неотрицательное число, характеризующее это преобразованиеА  supu 0Auu.(2.2)Введенную таким образом норму матрицы называют подчиненной соответствующей норме вектора.

Конкретный вид нормы матрицы в этомслучае зависит от выбранной нормы вектора. Укажем некоторые свойстванормы матрицы:||A + B|| ≤ ||A|| + ||B||,||λA|| = |λ| ||A||,||AB|| ≤ ||A||∙||B||,||A|| = 0 тогда и только тогда, когда А = 0.Говорят, что норма матрицы А согласована с нормой вектора u, есливыполнено условие34II.2.2.

Другие нормы в Rn. Теорема об эквивалентности норм||Au|| ≤ ||A|| ||u||.Нетрудно видеть, что подчиненная норма согласована с соответствующейметрикойвекторногопространства.Всамомделе,|| Au || || Au |||| A || supоткуда Au  A  u .|| u ||||u|| 0 || u ||Подчиненные введенным выше нормам векторов нормы матриц будут определяться следующим образом:nA 1  max  aij ,(2.3а)1i  n j 1nA 2  max  aij ,1 j  n i 1(2.3б)A 3  max  i ( A * A) .1i  n(2.3в)II.2.2. Другие нормы в Rn.

Теорема об эквивалентности норм1/ m nmРассмотрим следующее выражение: x(x)    xi  . Нетрудно i 1убедиться, что при любом натуральном m для величины x(x) выполненывсе аксиомы нормы (выше случаю (2.2а) соответствует предел при m → ∞,норме (2.2б) соответствует m = 1 и норме (2.2в) – m = 2. Часто такие нормы обозначают ||x||m в соответствии со значением параметра, при которомсумма вычисляется. Если не оговорено иное, такая нотация в задачах неприменяется. Существуют и другие нормы в линейном векторном пространстве.Для конечномерных пространств справедливо следующее утверждение.

Каковы бы не были две нормы ||•||a и ||•||b, то существуют положительные числа γ1, γ2 такие, что для всех элементов рассматриваемого пространства выполняется γ1||x||a ≤ ||x||b ≤ γ2||x||a . Числа γ1 и γ2 называются константами эквивалентности.Это утверждение называется теоремой об эквивалентности норм вконечномерных пространствах.В силу теоремы об эквивалентности норм все утверждения теоремверны для любых норм, поэтому ниже выбор нормы не конкретизируется.Естественно, в задачах требуется выбирать конкретную норму так, чтобырешение получалось самым легким способом.35II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫII.3.

Обусловленность СЛАУ. Число обусловленности матрицыПонятия согласованных норм матриц и векторов позволяют оценитьпогрешности, возникающие при численном решении СЛАУ. Пусть и матрица, и правая часть системы уравнений заданы с некоторой погрешностью, тогда наряду с системойAu = f(3.1)рассматривается возмущенная система(A + ΔA)(u + Δu) = f + Δf.Теорема 1. Пусть правая часть и невырожденная матрица СЛАУ(3.1) вида Au = f, u  R n , f  R n , получили приращения Δf и ΔA соответственно. Пусть существует обратная матрица А–1 и выполнены условия||A|| ≠ 0, μ||ΔA||/||A|| < 1, где μ = ||A||∙||A-1||. В этом случае оценка относительной погрешности решения ||Δu||/||u|| удовлетворяет неравенствуuu1 A fA .A  fAПри ΔA ≈ 0 получаем оценку при наличии погрешности только правых частейuuΔff.Это важное соотношение показывает, насколько возрастают относительные ошибки решения СЛАУ в случае наличия относительных погрешностей задания правых частей и элементов матриц.Величина μ = ||A||∙||A-1||, называется числом обусловленности матрицы A.

Она играет существенную роль во всех задачах прикладной линейной алгебры.Почти очевидно, что всегда μ ≥ 1. Действительно,1 = ||E|| = ||A-1A|| ≤ ||A-1|| ||A|| = μ.II.4. Решение систем линейных алгебраических уравнений(СЛАУ). Прямые и итерационные методыРассмотрим СЛАУ Au = f, где А – невырожденная (detA ≠ 0) квадратная матрица размером n × n, u = {u1, …,un}T – вектор-столбец решения,f = {f1,…,fn}T – вектор-столбец правой части.36Прямые методы решения СЛАУТак как матрица системы невырожденная, Δ = det A ≠ 0, то решениесистемы (2.1) существует и единственно.Прямые методы позволяют в предположении отсутствия ошибококругления (при проведении расчетов на идеальном, т. е.

бесконечноразрядном компьютере) получить точное решение задачи за конечное числоарифметических действий. Итерационные методы, или методы последовательных приближений, позволяют вычислить последовательность {uk},сходящуюся к решению задач при k → ∞ (на практике, разумеется, ограничиваются конечным k в зависимости от требуемой точности).Прямые методы решения СЛАУК прямым методам решения СЛАУ относятся правило Крамера [16],метод исключения Гаусса, поиск решения с помощью обратной матрицыи метод сопряженных градиентов. Правило Крамера неэкономично длясистем размерности выше трех (см.

пример в [4]). Метод сопряженныхградиентов, который является прямым методом решения СЛАУ, для систем большой размерности может использоваться как итерационный, т.е.вычисления прекращают, не завершая полный цикл вычислений. Неприятным свойством метода сопряженных градиентов является его возможная неустойчивость. Наиболее употребительным прямым методом решения СЛАУ является метод Гаусса и различные его модификации.II.4.1.

Метод исключения ГауссаПрямой ход метода Гаусса состоит в следующем.Положим, что a11 ≠ 0 и исключим u1 из всех уравнений, начиная совторого, для чего ко второму уравнению прибавим первое, умноженное на–a21/a11 = η21, к третьему прибавим первое, умноженное на –a31/a11 = η31, ит. д. После этих преобразований получим эквивалентную систему, коэффициенты и правые части которой определяются следующим образом:aij1 = aij – ηi1a1j; fi1 = fi – ηi1f1; i, j = 2, …, n.Без ограничения общности считаем, что a221 ≠ 0. В противном случаеменяем местами второе уравнение «новой» системы и первое уравнение, вкотором элемент во втором столбце отличен от нуля.Аналогично исключаем u2 из последних (n – 2) уравнений системы. Врезультате преобразований получим новую эквивалентную систему уравнений, в которой aij2  a1ij  i 2 a12 j ; fi2  fi1  i 2 f 21 ; i, j = 3, …, n.

Продолжая37II. ЭЛЕМЕНТЫ ПРИКЛАДНОЙ ЛИНЕЙНОЙ АЛГЕБРЫалгоритм, т.е. исключая ui (i = k + 1, …, n), приходим на n – 1 шаге к системе с треугольной матрицей.Обратный ход метода Гаусса позволяет определить решение системылинейных уравнений. Из последнего уравнения системы находим un; подставляем это значение в предпоследнее уравнение, получим un – 1. Поступая так и далее, последовательно находим un – 2, un – 3,…, u1.Вычисления компонент вектора решения проводятся по формулам( n1),un  f n(n1) / ann…1uk ( f ( k 1)  ak( k,k1)1uk 1 ( k 1) kakkk  n  1, n  2, ,1,…1u1 ( f1  a12u2 a11( k 1) aknun ), a1nun ).Этот алгоритм прост и легко реализуем при условии, что a11  0,a22  0,  Количество арифметических действий прямого хода  2/3n3,обратного  n2.В реальных вычислениях используются методы с выбором главного(или ведущего) элемента.

Выбор главного элемента по столбцам реализуется следующим образом: перед исключением u1 отыскивается max ai1 .iПусть максимум достигается при i = k. В этом случае меняются местамипервое и k уравнения (или в матрице меняются местами две строки) и реализуется процедура исключения.(1)Затем отыскивается max ai 2 , и процедура поиска главного элементаiв столбцах повторяется.

Так же реализуется выбор главного элемента построкам: перед исключением u1 отыскивается max a . Если максимумj kjдостигается при i = k, то у u1 и uk меняются номера, то есть максимальныйэлемент из коэффициентов первого уравнения окажется на месте а11, и т.д.Наиболее эффективным является метод Гаусса с выбором главного элемента по всей матрице.При использовании поиска главного элемента по строке необходимозапоминать совершенные перестановки, так как после завершения процедуры решения потребуется перестановка компонент векторного решения.38II.4.2. LU-разложениеВо многих методах важным является условие диагонального преобладанияaii n aijдля i = 1, …, n, при выполнении, которого проблемы,j 1j iпоявляющиеся в методе Гаусса, не возникают. Если для всех строк матрицы выполняются строгие неравенства, то говорят о строгом диагональном преобладании.II.4.2.

Характеристики

Список файлов книги