Численные методы. Соснин (2005) (1160462)

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

Текст из файла

Московский Государственный Университетимени М. В. ЛомоносоваФакультет Вычислительной Математики и КибернетикиЧисленные методы.Конспект лекций(VI семестр)составители —Д. В. Ховрато́вич, Е. А. Поповv. 1.01f — 19.03.2005ПредисловиеЭкзамен проходил под лозунгом «Вазелин — свой!».

. .Приветствуем вас, уважаемые читатели! Вообще говоря, в материалах такого рода авторы редкорешаются писать какую-нибудь отсебятину, предпочитая проговаривать ее при передаче распечаток изрук в руки. Тем не менее, мы решили донести до каждого читателя свои мысли и эмоции, возникавшиепри подготовке этого труда. Особо нервных просим перелистнуть страницу.То, что вы сейчас держите в руках или читаете с экрана, является абсолютно неофициальнымконспектом абсолютно официальных лекций по курсу, как ни странно, «Численные методы», прочитанных на факультете ВМиК МГУ. В конспект было вложено много сил и труда, и, как ни противнонам снова садиться за этот чертов TEX, мы просим всех людей, нашедших в этом материале ошибкиили опечатки, сообщить о них нам. Особо мы будем признательны тем, кто не только сообщит обошибке, но и скажет, где она находится.

За все глюки просим прощения заранее, но себя не виним, таккак в работах такого объема они, как известно, неизбежны.Авторы выражают искреннюю благодарность: лектору Соснину Николаю Васильевичу, читавшему данный курс; своим друзьям и верным помощникам: Поспелову Алексею, Коваль Анне, АнтоновойЕкатерине. Кроме того, авторы благодарны друг другу и самим себе: без многих из нас этот труд никогда не был бы написан.

Отдельная благодарность тем, кто не мешал (например, Рябцеву Владимиру —а ведь мог бы!).Особая благодарность Дональду Кнуту и Лесли Лэмпорту.Находили и исправляли ошибки: Антонова Екатерина, Коваль Анна, Корнеев Андрей, КругловаЕлена, Поспелов Алексей, Рябцев Владимир, Смирнов Иван.Примечание. Все сноски являются собственностью авторов. Все фразы, где встречаются слова«утверждается» и «известно», следует воспринимать как нестрогие ссылки на недоказываемыеутверждения.23Краткая история создания лекций по численным методам.Отсчет по версиям0.1, 28.02.2003 Нумерация введена, чтобы не запутаться. Набрана смешная лекция.0.12, 11.03 Набрана часть первой главы.0.19, 16.04 Набраны четыре главы.

Дмитрий Ховратович чувствует, что его это уже слегка напрягает. Евгений Попов полон сил и энергии.0.35, 27.04 Пятая глава подходит к середине. Самое зло — интегро-интерполяционный метод — позади.0.45, 13.05 Последняя лекция прочитана. Последние разделы, набранные Дмитрием Ховратовичем. Авторы хотят разделаться с конспектом до начала зачетной сессии и надеются получить экзаменавтоматом.

Кроме того, это первый вариант, выложенный в открытое пользование.0.65, 16.05 Номер сильно повышен, хотя это ни о чем не говорит. Пока ничего не готово.0.7, 18.05 Все готово. Последняя часть набиралась в общаге в страшной спешке. После этого распечатанаи торжественно принесена лектору.0.71, 18.05 Вечером того же дня найдены несколько ошибок, а фразы про укурков снова появились в конспекте.0.79, 12.06 После сдачи досрочного экзамена авторы исправляют около 200 ошибок, а Алексей Поспеловделает картинки. К сожалению, полностью они еще не готовы.0.80, 13.06 Картинки готовы все.

Теперь это все занимает 113 страниц.0.81, 15.06 Иван Смирнов находит еще ошибки. Это находит отражение в лекциях.0.82, 16.06 Исправлено чуть-чуть.0.85, 22.06 Круглова Елена, Коваль Анна и Корнеев Андрей исправляют еще около 30 ошибок. Сессия близится к концу.0.86, 23.06 Версия, сделанная в ночь перед экзаменом для 318, 319 группы. Просто исправлено еще около15 ошибок.0.90, 26.06 Экзамены кончились.

Исправлены еще около 50 ошибок и чуть подкорректированы картинки.Следующая версия будет финальной.1.00, 04.06.2004 Исправлены пара-тройка мелких багов. Но зато - релиз!1.01, 19.03.2005 Добавлена история сборки. Коллектив авторов на этом завершил свою работу и передал правона дополнения следующим поколениям.

Удачи всем на экзаменах! ВМиК рулит!Глава 1Решение систем линейныхалгебраических уравненийВ данной главе мы будем рассматривать следующую задачу — требуется решить систему линейныхалгебраических уравнений (в дальнейшем СЛАУ), задаваемых в виде матричного уравнения:Ax = F,где A = (aij ) — матрица размерности n×n, причем det A 6= 0; x = (x1 , x2 , . .

. , xn )T — вектор-столбецнеизвестных, F = (f1 , f2 , . . . , fn )T — заранее заданный вектор-столбец правой части.Далее мы будем предполагать, что у всех рассматриваемых задач решение существует и единственно (в данном случае это следует из того, что определитель матрицы A не равен нулю).Рассмотрим несколько методов решения СЛАУ. Методы решения делятся на прямые, где мы получаем x за конечное число действий, и итерационные — получаем x как предел некоторой сходящейсяпоследовательности {xk } : x = lim xk .k→∞В случае прямых методов получается точное (до погрешности аппаратуры) решение.

В итерационных методах вводится точность решения ε > 0. Если |xk −x| < ε (x — точное решение) — заканчиваемпроцесс вычислений, иначе — вычисляем очередное xk+1 и т. д.К прямым методам относятся формулы Крамера, метод Гаусса. К итерационным методам — методЗейделя, метод верхней релаксации и т.д.Основным показателем при оценке эффективности метода является его сложность. В прямыхметодах это чаще всего количество арифметических операций, необходимых для вычисления x, а витерационных — количество итераций, необходимых для достижения заданной точности ε (его записывают как k0 (ε)).

К примеру, метод Крамера (модифицированный) имеет сложность O(n4 ), а методГаусса — O(n3 ).Выбор метода, в основном, зависит от размерности матрицы. При решении систем большой размерности чаще используют итерационные методы.1.1Прямые методы решения СЛАУ. Метод квадратного корняВ этой главе мы рассмотрим несколько прямых методов для решения системыAx = F.(1.1)В самом общем случае используется метод Гаусса1 , в котором мы будем выделять прямой ход —приведение матрицы коэффициентов к верхнетреугольному виду (мы думаем, что все читатели знают,1 Впервые описан К. Гауссом в 1849г., правда, без обратного хода.

Этот же метод часто называют методом ГауссаОстроградского.41.1. ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ. МЕТОД КВАДРАТНОГО КОРНЯ5как это делается), и обратный ход — приведение верхнетреугольной матрицы к диагональной инахождение самого решения.Однако существует целый класс методов, использующих специфику конкретной матрицы — например, метод прогонки.Метод прогонки имеет сложность O(n), но он применим только к трехдиагональным матрицам.Вычисление элементов обратной матрицыЧтобы решить систему (1.1), можно вычислить A−1 , тогда решение будет представимо в видеx = A−1 F.Для определения элементов матрицы A−1 рассмотрим уравнение AA−1 = E, где матрица A —задана, а требуется найти A−1 .Обозначим за aij элементы матрицы A, а за zij — элементы матрицы A−1 .

Умножая строкиматрицы A на столбцы A−1 (по определению произведения матриц), получим n2 алгебраическихуравнений:nXail zlj = δij , i, j = 1, n.l=1Эти уравнения можно объединить в группы с фиксированным индексом j, то есть у нас получитсяпо n уравнений для определения каждого столбца матрицы A−1 .Это будут уравнения вида Az j = ej , где z j — j-й столбец матрицы A−1 , а ej — j-й столбецматрицы E.

Получаем n систем по n уравнений в каждой. Далее используем метод Гаусса решениясистем уравнений, при этом сложность данного метода будет равна O(n4 ).Кроме того, можно применить прямой ход метода Гаусса сразу ко всем системам (т. к. матрица3A — общая для всех систем), и сложность метода станет ≈ n3 .Наложим ограничения на матрицу A из уравнения (1.1).Определение. Матрица A называется положительно определенной, если выполнено одно изусловий (они эквивалентны друг другу):1. все главные миноры больше нуля;2. все собственные числа матрицы A (далее обозначаются как λ(A)) положительны;3.

∀ x 6= 0hAx, xi > 0.Примечание. Из пункта 1 (а также из 3) определения следует необходимое условие положительной определенности — все диагональные элементы положительны.Достаточным условием положительной определенности является условие диагонального преnX|aij |, то матрица A = (aij ) положительно определена.обладания: если элементы aii >j=1j6=iМетод квадратного корняБудем рассматривать симметричные (т.

е. A = AT ) положительно определенные матрицы. Длятаких матриц справедливо представление (разложение Холецкого):A = LLT ,(1.2)6Глава 1. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙгде L — нижнетреугольная матрица:l11L=0......lij..0.. . .0 .lnnРассмотрим задачу (1.1). Подставив разложение (1.2) для A в уравнение (1.1), получим:LLT x = F.Обозначим LT x = y, тогда получим систему уравнений относительно новой переменной y :Ly = F.Учитывая то, что матрица L нижнетреугольная, для решения этой системы требуется только обратный ход метода Гаусса (решение уравнений построчно сверху вниз). Аналогично, так как y = LT x,то нужно решать только СЛАУ с верхней треугольной матрицей. Поэтому основной вклад в сложность3даст вычисление элементов матрицы L — и общая сложность метода будет приближенно равна n6 .Теперь покажем, что матрицу L можно найти.

Обозначим L = (lij ), LT = (lij ) — из определениятранспонированной матрицы вытекает, что lij = lji . Найдем элементы этих матриц, для чего распишемразложение (1.2):l11 0 . . . 0l11..  ...... lij.  0 = (aij ).LLT = .......lij . 0   .lnn0 .

. . 0 lnnПо правилу умножения двух матриц получаем:aij =nXmin(i, j)lil llj = {учитывая треугольный вид матриц} =l=1Xlil llj .l=1Найдем элементы lij матрицы L. Сначала вычислим l11 :a11 = l11 l11=⇒2a11 = l11=⇒l11 =√a11(a11 > 0).Получив l11 , найдем элементы первого столбца матрицы L:ai1 = li1 l11 = li1 l11=⇒li1 =ai1,l11i = 2, n.Рассмотрим второй столбец матрицы A :ai2 = li1 l12 + li2 l22=⇒li1 l21 + li2 l22 = ai2 ,i = 2, n.(1.3)2222= a22 =⇒ l22= a22 − l21— а l21 уже найдено.Пусть i = 2, тогда l21+ l22Извлекая корень, получим:sssq22aaa11 a22 − a2212 =l22 = a22 − l21a22 − 221 =⇒ l22 = a22 − 21 =.l11a11a11a11 a12 2 > 0 по условию положиКорректность вытекает из того, что a11 > 0, a11 a22 − a12 = a21 a22 тельной определенности матрицы A.1.1.

ПРЯМЫЕ МЕТОДЫ РЕШЕНИЯ СЛАУ. МЕТОД КВАДРАТНОГО КОРНЯ7Подставив в (1.3) только что вычисленное значение l22 , получим представление для остальныхэлементов второго столбца:ai2 − li1 l21li2 =,i = 3, n.l22Рассмотрим произвольный ( k-й ) столбец матрицы A :li1 l1k + li2 l2k + . . .

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций