Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011).pdf), страница 5

И. В. Семушин, доц. Ю. В. ЦыгановаСодержание:Этот курс излагает численные методы решения задач линейной алгебры: решениесистем уравнений, обращение матриц, вычисление определителей, решение нелинейных уравнений, аппроксимация функций и отыскание собственных значенийматриц. Программа курса охватывает: методы исключения неизвестных, разложения Холесского, ортогональные преобразования, итерационные методы, метод наименьших квадратов, устойчивые алгоритмы оценивания и обзор методов решенияпроблемы собственных значений.Ожидаемые результаты изучения: продемонстрировать —структуры погрешностей решения вычислительных задач; корректности задач; прямых и итерационных методов для системзнание иуравнений; задачи и алгоритмов метода наименьших квадратов;понимание:проблемы собственных значений и основ ее решения.способность:понимать и формулировать основные численные процедуры и(теоретическиерешать демонстрационные задачи; идентифицировать подходянавыки)щие методы для конкретных задач линейной алгебры.понимать реализацию и поведение численных методов и решеспособность:ний на практике; логически формулировать численные методы(практическиедля решения задач на компьютере с применением языков пронавыки)граммирования (C #, Pascal или C/C++).изучать предмет самостоятельно; использовать литературныеспособность:источники; использовать персональный компьютер для про(ключевыеграммирования; эффективно конспектировать материал и раснавыки)поряжаться рабочим временем.Оценивание: 5 % за посещаемость (неуважительные пропуски прогрессивно штрафуются); 30 % за семестровые (домашние) задания, 65 % суммарно за три контрольные работы и финальный (устный) экзамен.Практическая работа: Выдаваемые индивидуальные задания включают программирование отдельных методов из числа методов, излагаемых в данном курсе.Рекомендуемые учебные материалы: Конспект лекций.В.

В. Воеводин. Численные методы алгебры. Теория и алгоритмы. — М.: Наука, 1966.А. А. Самарский, А. В. Гулин. Численные методы. — М.: Наука, 1989.Дополнительное чтение: Н. Н. Калиткин. Численные методы. — М.: Наука, 1978.Н. С. Бахвалов. Численные методы. — М.: Наука, 1975. или: Н. С. Бахвалов,Н.

П. Жидков, Г. М. Кобельков. Численные методы. — М.: Наука, 1987.ab24Число кредитных часов (приравнивается числу аудиторных часов в неделю).Продолжительность курса.IВычислительная линейная алгебра2Стандартные алгоритмыLU -разложения2.1Алгоритмы метода ГауссаОбычный метод Гаусса, осуществляющий LU -разложение матрицы A [12,5, 4, 9, 97], заключается в последовательном исключении переменных изуравнений системыAx = f.(2.1)На первом шаге для исключения первой переменной x1 из всех уравнений,лежащих в системе ниже первого уравнения, первое уравнениеa11 x1 + a12 x2 + .

. . + a1n xn = f1(2.2)объявляем ведущим уравнением. Это возможно только при a11 6= 0. Тогда,разделив обе части (2.2) на a11, это ведущее уравнение получим в виде, вкотором коэффициент при x1 окажется равен 1. Заметим, что эта 1 — строгая (т. е. не приближенная) величина. Это действие — деление уравнения наведущий элемент (на первом шаге это a11 6= 0) — удобно называть нормировкой.Второе действие заключается в серии вычитаний ведущего уравнения извсех нижележащих уравнений, чтобы исключить из них неизвестную x1. Дляэтого умножаем пронормированное уравнение на ai1 и вычитаем результатиз i-го уравнения системы (2.1), i = 2, .

. . , n. На этом заканчивается первыйшаг алгоритма. После первого шага система (2.1) приведена в виду:(1)(1)(1)1 · x1 + a12 x2 + . . . + a1n xn = f1 , (1)(1)(1) a22 x2 + . . . + a2n xn = f2 ,(2.3)...(1)(1)(1) an2 x2 + . . . + ann xn = fn .2 Стандартные алгоритмы LU-разложенияЭто второе действие удобно называть обновлением активной подсистемы(активной подматрицы), т. е.

той части системы уравнений (матрицы A),где еще будут продолжаться подобного рода действия.На втором шаге метода Гаусса описанный алгоритм повторяем для переменной x2, т. е. берем систему (2.3), объявляем ведущим второе уравнение(1)(для этого нужно иметь a22 6= 0) и нормируем в ней второе уравнение.Получаем его в виде(2)(2)(2)1 · x2 + a23 x3 + . . . + a2n xn = f2(верхний индекс в скобках указывет номер шага, после которого получен текущий результат). После этого исключаем переменную x2 из оставшихся n − 2 уравнений системы (2.3). Таким образом, любой полный шагалгоритма метода Гаусса состоит из двух действий: сначала нормировкаведущей строки матрицы, потом обновление (серия вычитаний) в активнойподматрице.После n − 1 полных шагов и n-го неполного шага (поскольку ниже n-говедушего уравнения больше нет уравнений) получим две системы линейныхалгебраических уравненийLy = f,Ū x = y,(2.4)эквивалентных исходной системе (2.1), где L — нижняя треугольная матрица и Ū верхняя треугольная матрица, на диагонали которой стоят единицы1 .

При этом k-й столбец матрицы L (его нетривиальная, т. е. ненулевая часть) запоминает числа для двух действий на k-м шаге алгоритма, аименно: элемент lkk является ведущим элементом, производившим нормировку k-го уравнения, в то время как элементы lki, i = k + 1, k + 2, . . .

, nявляются теми коэффициентами, на которые было умножено пронормированное ведущее (k-е) уравнение, чтобы результатом последующего его вычитания из нижележащих уравнений было исключение из них неизвестного xk .Можно говорить, что роль матрицы L — сохранять «историю» нормировоки вычитаний в процессе исключения неизвестных по методу Гаусса. Рольматрицы Ū — иная.

Матрица Ū представляет собою тот эквивалентный видсистемы (2.1), который она приобретет по завершении этого процесса.Определение 2.1. Определители ∆i подматриц, получаемых оставлением первых i строк и первых i столбцов матрицы, называют главнымиминорами матрицы.128Здесь и далее черта над матрицей означает, что на главной диагонали стоят строгие единицы.2.1 Алгоритмы метода ГауссаТеорема 2.1. Если все главные миноры матрицы A в системе (2.1)отличны от нуля, то процесс Гаусса исключения неизвестных, протекающийв прямом направлении, — начиная от первого неизвестного x1 и от первогоуравнения системы, — эквивалентен разложению A = LŪ, которое существует и единственно с нижней треугольной невырожденной матрицей L иверхней треугольной матрицей Ū с единичной диагональю.Доказательство.матрицы [12].Докажите самостоятельно индукцией по размеру n2После разложения вводят правую часть f данной системы (2.1) и находятвектор y решения называется прямой подстановкой:!i−1Xyi = fi −lij yj lii−1, i = 1, 2, .

. . , n.j=1Далее вторая система из (2.4) так же легко решается процедурой обратнойподстановки:xi = yi −nXj=i+1uij xj ,i = n − 1, . . . , 1,xn = yn .Замечание 2.1. Пересчет элементов вектора f должен быть отложен, т. е. сначала пересчет коэффициентов матрицы A должен привестик разложению матрицы A в произведение матриц L и Ū и только затемдолжна быть введена и соответственно обработана правая часть — векторf . При этом вектор y замещает f и затем x замещает y, — экономия памяти.Алгоритм LŪ -разложения матрицы A запишем следующим образом:Для k = 1 до nНормируем первую строку матрицы A(k−1) .Для i = k + 1 до nВычитаем первую строку матрицы A(k−1) ,(k−1)умноженную на aik , из i-й строки.Здесь A(k−1) означает активную подматрицу матрицы A после (k − 1)-гoшага метода Гаусса, k = 1, 2, .

. . , n, причем A(0) = A.Алгоритм L̄U -разложения матрицы A отличается только нормировкойэлементов активной подматрицы:292 Стандартные алгоритмы LU-разложенияДля k = 1 до n − 1Нормируем первый столбец матрицы A(k−1).Для i = k + 1 до nВычитаем первую строку матрицы A(k−1) ,(k−1)умноженную на aik , из i-й строки.Упражнение 2.1.Измените направление процесса Гаусса на обратное. Докажите, что если процесс Гаусса исключения неизвестных вести отпоследнего неизвестного xn и от последнего уравнения системы, двигаясьвверх по нумерации уравнений и влево по нумерации исключаемых неизвестных, то получим разложение A = U L̄ (если нормировать строки) и A = Ū L(если нормировать столбцы). Докажите соответствующие теоремы — аналоги теоремы 2.1. Для этого измените определение 2.1 главных миноров.Описанные выше алгоритмы в том виде, в каком они приведены, на практике используются очень редко, т.

е. только в том случае, если можно гарантировать, что в результате гауссова исключения на диагонали не появятся нулевые элементы. Однако это можно гарантировать только для матриц специального вида (например, для положительно определенных матриц,см. разд. 6), поэтому в общем случае используется метод Гаусса с выборомглавного (ведущего) элемента.2.2Выбор ведущего элементаОпределение 2.2. Матрицей перестановок P называют квадратнуюматрицу, в которой каждая строка, а также каждый столбец, содержит одинненулевой элемент, равный 1.Определение 2.3. Элементарной матрицей перестановок Pij называют квадратную матрицу, полученную из единичной матрицы перестановкой двух строк: i-й и j-й, либо перестановкой двух столбцов: i-го и j-го (обаварианта перестановок дают один и тот же результат).Упражнение 2.2.Докажите справедливость следующих утверждений:1.

Произведение Pij A производит в A перестановку i-й и j-й строк.2. Произведение APij производит в A перестановку i-го и j-го столбцов.302.2 Выбор ведущего элемента3. Pij Pij = I — свойство идемпотентности матриц Pij .4. Любая матрица перестановок P может быть разложена в произведениеэлементарных матриц перестановок.5. P −1 = P T — свойство ортогональности матриц перестановок P .Теорема 2.2. Если det A 6= 0, то существуют матрицы перестановокP и Q, такие что все угловые (т.

е. главные) миноры матрицы P A, равно каки матриц AP и AP Q, отличны от нуля.Доказательство. Докажите индукцией по размеру матрицы A [12]. 2Следствие 2.1. Если det A 6= 0, то существуют матрицы перестановокP и Q, такие что следующие варианты разложения матрицы A существуюти единственны: P A = LŪ, P A = L̄U , AP = LŪ , AP = L̄U , P AQ = LŪ ,P AQ = L̄U .2Отсюда видны три стратегии выбора главного (ведущего) элемента: постолбцу, по строке и по активной подматрице.Стратегия I. Первая стратегия (по столбцу) подразумевает, что вкачестве главного на k-м шаге метода Гаусса выбирается максимальныйпо модулю элемент первого столбца активной подматрицы. Затем этот элемент меняется местами с диагональным элементом, что соответствует перестановке строк матрицы A(k−1) и элементов вектора f (k−1) .