Методическое пособие для практических и лабораторных работ по курсу «Численные методы»

85
Министерство образования и науки РФ
Сибирский федеральный университет
Институт естественных и гуманитарных наук
Факультет математики и информатики
Кафедра вычислительных и информационных технологий



Распопов В.Е., Клунникова М.М.


Лекции по курсу
«Численные методы»








Красноярск 2007

86
Министерство образования и науки РФ
Сибирский федеральный университет
Институт естественных и гуманитарных наук
Факультет математики и информатики
Кафедра вычислительных и информационных технологий





Распопов В.Е., Клунникова М.М.


Методическое пособие для практических и лабораторных работ по курсу
«Численные методы»

87
Красноярск 2007

88
Министерство образования и науки РФ
Сибирский федеральный университет
Институт естественных и гуманитарных наук
Факультет математики и информатики
Кафедра вычислительных и информационных технологий





Распопов В.Е., Клунникова М.М.


Презентации по курсу
«Численные методы»







Красноярск 2007

89
Содержание
Лекция 1.
Математическое моделирование и вычислительный эксперимент. Численные методы как раздел современной математики. Роль компьютерно ориентированных численных методов в исследовании сложных математических моделей.
4
Лекция 2.
Классификация погрешностей.
Абсолютная и относительная погрешности числа и функции. Прямая и обратная задачи теории погрешностей.
Неустойчивые алгоритмы.
Особенности машинной арифметики. Задачи вычислительной алгебры. Прямые и итерационные методы.
10
Лекция 3.
Метод исключения неизвестных (метод Гаусса) решения систем линейных алгебраических уравнений (СЛАУ). Схема единственного деления. Метод Гаусса с выбором главного элемента. LU – разложение матрицы. Методы вращений, квадратного корня.
19
Лекция 4.
Векторные и матричные нормы. Согласованность норм.
Обусловленность СЛАУ. Число обусловленности матрицы.
Вычисление определителей. Обращение матриц.
36
Лекция 5.
Ортогональные преобразования. Матрицы вращения и отражения. QR- и HR-разложения матриц.
45
Лекция 6.
Метод прогонки решений СЛАУ с трехдиагональной матрицей. Устойчивость. Корректность. Варианты метода прогонки. Возможность распараллеливания расчетов.
53
Лекция 7.
Итерационные методы. Стационарные. Нестационарные.
Теоремы сходимости. Метод Якоби. Метод Гаусса-Зейделя.
Каноническая форма итерационных методов. Сходимость.
61
Лекция 8.
Метод простой итерации. Сходимость. Метод релаксации.
Сходимость. Метод наискорейшего спуска. Метод минимальных невязок. Метод сопряженных градиентов.
68
Лекция 9.
Полная и частичная проблема собственных значений.
Прямые и итерационные методы. Степенной метод вычисления максимального по модулю собственного числа. Метод скалярных произведений. Методы исчерпывания.
77
Лекция 10.
Метод Якоби решения полной проблемы собственных значений для симметричной матрицы. QR- метод. Уточнение собственных чисел и векторов. Оценки собственных чисел.
85

90
Теоремы Гершгорина.
Лекция 11.
Вычисление корней нелинейных уравнений. Отделение корней. Метод деления отрезка пополам. Метод хорд. Методы простой итерации, Ньютона. Модификации метода Ньютона.
Сходимость. Метод Вегстейна.
97
Лекция 12.
Решение систем нелинейных уравнений. Методы простой итерации, Зейделя, Ньютона. Сходимость.
106
Лекция 13.
Интерполяция.
Существование и единственность обобщенного интерполяционного многочлена. Интерполирование алгебраическими многочленами. Интерполяционные полиномы
Лагранжа и Ньютона. Оценка погрешности интерполяции.
112
Лекция 14.
Многочлены Чебышева. Оптимизация погрешности интерполяции. Сходимость интерполяционного процесса. Сплайн- интерполирование. Построение кубического сплайна.
122
Лекция 15.
Наилучшее приближение в линейном нормированном пространстве. Существование и единственность элемента наилучшего приближения. Многочлен наилучшего приближения.
Наилучшее приближение в гильбертовом пространстве. Метод наименьших квадратов. Аппроксимация функций многих переменных.
136
Лекция 16.
Интерполяционные квадратурные формулы.
Квадратурные формулы прямоугольников, трапеций, Симпсона.
Погрешность. Правило Рунге оценки погрешности.
149
Лекция 17.
Квадратурные формулы наивысшей алгебраической степени точности. Построение. Погрешность. Устойчивость.
Интегрирование функций специального вида.
157
Лекция 18.
Приближенное вычисление кратных интегралов. Метод
Монте-Карло. Формулы численного дифференцирования. Оценка погрешности. Некорректность. Регуляризация. Понятие сеточной функции. Простейшие операторы конечных разностей.
166
Литература
178

91
Лекция 1: Математическое моделирование и вычислительный эксперимент. Численные методы как раздел современной математики. Роль компьютерно-ориентированных численных методов в исследовании сложных математических моделей.
В современном мире математика все больше и больше становится одним из важных инструментов познания человеком окружающего мира.
Математика является основным методом теоретического исследования и практическим орудием в естествознании и технике, без математики совершенно невозможно проводить серьезные научные и инженерные расчеты. Недаром родоначальник немецкой классической философии
Иммануил Кант (1742 – 1804 гг.) утверждал, что «в каждой отдельной естественной науке можно найти собственно науку лишь постольку, поскольку в ней можно найти математику». Математика, как наука, возникла в связи с необходимостью решения практических задач: измерений на местности, навигации и т.д. Вследствие этого математика всегда была численной математикой, ее целью являлось получение решения задач в виде числа.
Создание ЭВМ дало новый толчок развитию математики, появились новые дисциплины «математическая экономика», «математическая химия»,
«математическая лингвистика» и т. д. Возникло понятие «математическое моделирование».
Слово «Модель» происходит от латинского modus (копия, образ, очертание). Моделирование – это замещение некоторого объекта А
(оригинала) другим объектом Б (моделью).
Математическая модель — это упрощенное описание реальности с помощью математических понятий.
Математическое моделирование — процесс построения и изучения математических моделей реальных процессов и явлений, т.е. метод исследования объектов и процессов реального мира с помощью их приближенных описаний на языке математики – математических моделей.
Крупнейшие ученые прошлого сочетали в своих трудах как построение математического описания явлений природы (математические модели), так и его исследования. Анализ усложненных моделей требовал создания новых, как правило, численных методов решения задач.
Основоположником отечественного математического моделирования справедливо считают академика А.А.Самарского. Он выразил методологию математического моделирования знаменитой триадой «модель – алгоритм –
программа».
1 этап. Модель. Выбирается или строится модель исследуемого объекта, которая в математической форме отражает его важнейшие свойства.
Обычно математические модели реальных процессов достаточно сложны и

92
включают в себя системы нелинейных функционально-дифференциальных уравнений. Ядром математической модели, как правило, являются уравнения с частными производными. Для получения предварительных знаний об объекте построенная модель исследуется традиционными аналитическими средствами прикладной математики.
2 этап. Алгоритм. Выбирается или разрабатывается вычислительный алгоритм для реализации построенной модели на компьютере, который не должен искажать основные свойства модели, должен быть адаптирующимся к особенностям решаемых задач и используемым вычислительным средствам. Проводится изучение построенной математической модели методами вычислительной математики.
3 этап. Программа. Создается программное обеспечение для реализации модели и алгоритма на компьютере. Создаваемый программный продукт должен учитывать важнейшую специфику математического моделирования, связанную необходимостью использования набора математических моделей и многовариантностью расчетов.
В результате исследователь получает в руки универсальный, гибкий и недорогой инструмент, который сначала отлаживается, тестируется и калибруется на решении набора пробных задач. Затем проводится широкомасштабное исследование математической модели для получения необходимых качественных и количественных свойств и характеристик исследуемого объекта.
Предложенная методология получила свое развитие в виде технологии
«вычислительного эксперимента».
Вычислительный эксперимент – это информационная технология, предназначенная для изучения явлений окружающего мира, когда натурный эксперимент оказывается либо невозможен (например, при изучении здоровья человека), либо слишком опасен (например, при изучении экологических явлений), либо слишком дорог и сложен (например, при изучении астрофизических явлений).
Широкое применение ЭВМ в математическом моделировании, разработанная теория и значительные практические результаты позволяют говорить о вычислительном эксперименте, как о новой технологии и методологии научных и практических исследований. Серьезное внедрение вычислительного эксперимента в инженерную деятельность еще не очень широко, но там, где оно происходит реально (в авиационной и космической промышленности) его плоды весьма весомы.
Отметим некоторые достоинства вычислительного эксперимента по сравнению с натурным. Вычислительный эксперимент, как правило, дешевле физического. В этот эксперимент можно легко и безопасно вмешиваться. Его можно повторить еще раз, если это необходимо, и прервать в любой момент.

93
В ходе этого эксперимента можно смоделировать условия, которые нельзя создать в лаборатории.
В ряде случаев проведение натурного эксперимента затруднено, а иногда и невозможно. Часто проведение полномасштабного натурного эксперимента сопряжено с губительными или непредсказуемыми последствиями (ядерная война, поворот сибирских рек) или с опасностью для жизни или здоровья людей. Нередко требуется исследование и прогнозирование катастрофических явлений (авария ядерного реактора АЭС, глобальное потепление или похолодание климата, цунами, землетрясение). В этих случаях вычислительный эксперимент может стать основным средством исследования. С его помощью оказывается возможным прогнозировать свойства новых, еще не созданных конструкций и материалов на стадии их проектирования. В то же время нужно помнить, что применимость результатов вычислительного эксперимента ограничена рамками принятой математической модели.
В отличие от натурных исследований вычислительный эксперимент позволяет накапливать результаты, полученные при исследовании какого- либо круга задач, а затем эффективно применять их к решению задач в других областях. Например, уравнение нелинейной теплопроводности описывает не только тепловые процессы, но и диффузии вещества, движения грунтовых вод, фильтрации газа в пористых средах. Изменяется только физический смысл величин, входящих в это уравнение.
После проведения первого этапа вычислительного эксперимента может возникнуть необходимость в уточнении модели. На втором этапе учитываются дополнительные эффекты и связи в изучаемом явлении, либо возникает необходимость пренебречь некоторыми закономерностями и связями. Затем этот процесс повторяют до тех пор, пока не убеждаются, что модель адекватна изучаемому объекту.
Обычно в процессе математического моделирования и вычислительного эксперимента участвуют помимо профессиональных математиков и программистов специалисты в конкретной предметной области (биологии, химии, медицине и др.).
Первый серьезный вычислительный эксперимент был проведен в СССР в 1968 году группой ученых под руководством академиков А. Н. Тихонова и
А. А. Самарского. Это было открытие, так называемого, эффекта Т-слоя
(температурного токового слоя в плазме, которая образуется в МГД- генераторах) – явления, которого на самом деле никто не наблюдал. И только через несколько лет Т-слой был зарегистрирован в экспериментальных физических лабораториях и технологам и инженерам окончательно стал ясен принцип работы МГД-генератора с Т-слоем.
В последние годы ряд Нобелевских премий по химии, медицине, экономике, физике элементарных частиц были присуждены работам,

94
методологическую основу которых составляло именно математическое моделирование.
Математические модели для описания изучаемых явлений в механике, физике и других точных науках естествознания использовались издавна. 3-4 тысячи лет назад решали задачи прикладной математики, связанные с вычислением площадей и объёмов, расчетами простейших механизмов, т.е. с несложными задачами арифметики, алгебры и геометрии. Вычислительными средствами служили собственные пальцы, а затем – счёты. Большинство вычислений выполнялось точно, без округлений.
В 17 веке Исаак Ньютон полностью описал закономерности движения планет вокруг Солнца, решал задачи геодезии, проводил расчёты механических конструкций.
Задачи сводились к обыкновенным дифференциальным уравнениям, либо к алгебраическим системам с большим числом неизвестных, вычисления проводились с достаточно высокой точностью до 8 значащих цифр. При вычислениях использовались таблицы элементарных функций, арифмометр, логарифмическая линейка; к концу этого периода появились неплохие клавишные машины с электромотором.
В это время были разработаны алгоритмы численных методов, которые до сих пор занимают почетное место в арсенале вычислительной математики.
Так Ньютон предложил эффективный численный метод решения алгебраических уравнений, а Эйлер – численный метод решения обыкновенных дифференциальных уравнений.
Классическим примером применения численных методов является открытие планеты Нептун. Уран планета, следующая за Сатурном, который много веков считался самой из далеких планет. К 40-м годам XIX в. точные наблюдения показали, что Уран едва заметно уклоняется от того пути, по которому он должен следовать с учетом возмущений со стороны всех известных планет. Леверье (во Франции) и Адамс (в Англии) высказали предположение, что, если возмущения со стороны известных планет не объясняют отклонение в движении Урана, значит, на него действует притяжение еще не известного тела. Они почти одновременно рассчитали, где за Ураном должно быть неизвестное тело, производящее своим притяжением эти отклонения. Они вычислили орбиту неизвестной планеты, ее массу и указали место на небе, где в данное время должна была находиться неведомая планета. Эта планета и была найдена в телескоп на указанном ими месте в 1846 г. Ее назвали Нептуном. Для расчета траектории
Нептуна Леверье понадобилось полгода.
Численное решение прикладных задач всегда интересовало математиков. Разработкой численных методов занимались крупнейшие ученые своего времени: Ньютон, Эйлер, Лобачевский, Гаусс, Эрмит,
Чебышев и др. Численные методы, разработанные ими, носят их имена.
Развитие численных методов способствовало постоянному расширению

95
сферы применения математики в других научных дисциплинах и прикладных разработках.
Появление ЭВМ дало мощный импульс еще более широкому внедрению численных методов в практику научных и технических расчетов.
Скорость выполнения вычислительных операций выросла в миллионы раз, что позволило решить широкий круг математических задач, бывших до этого практически не решаемыми.
Разработка и исследование вычислительных алгоритмов, их применение к решению конкретных задач составляет содержание огромного раздела современной математики
– вычислительной математики.
Вычислительная математика как самостоятельная математическая дисциплина сформировалась в начале двадцатого века. Вычислительную математику определяют в широком смысле как раздел математики, исследующий широкий круг вопросов, связанных с использованием ЭВМ. В узком смысле вычислительную математику определяют как теорию численных методов и алгоритмов решения поставленных математических задач. В нашем курсе вычислительную математику будем понимать в узком смысле этого термина.
Современные компьютерно-ориентированные численные методы должны удовлетворять многообразным и зачастую противоречивым требованиям. Обычно построение численного метода для заданной математической модели разбивается на два этапа: дискретизацию исходной математической задачи и разработку вычислительного алгоритма, позволяющего отыскать решение дискретной задачи. Выделяют две группы требований к численным методам. Первая группа связана с адекватностью дискретной модели исходной математической задаче, вторая – с реализуемостью численного метода на имеющейся вычислительной технике.
К первой группе относятся такие требования, как сходимость численного метода, выполнение дискретных аналогов законов сохранения, качественно правильное поведение решения дискретной задачи.
Предположим, что дискретная модель математической задачи представляет собой систему большого числа алгебраических уравнений.
Обычно, чем точнее мы хотим получить решение, тем больше уравнений приходится брать. Говорят, что численный метод сходится, если при неограниченном увеличении числа уравнений решение дискретной задачи стремится к решению исходной задачи.
Поскольку реальный компьютер может оперировать лишь с конечным числом уравнений, на практике сходимость, как правило, не достигается.
Следовательно, очень важно уметь оценивать погрешность метода в зависимости от числа уравнений, составляющих дискретную модель. По этой же причине стараются строить дискретную модель таким образом, чтобы она правильно отражала качественное поведение решения исходной задачи даже

96
при сравнительно небольшом числе уравнений. Так при дискретизации задач математической физики приходят к разностным схемам, представляющим собой системы линейных или нелинейных алгебраических уравнений.
Дифференциальные уравнения математической физики являются следствиями интегральных законов сохранения. Поэтому естественно требовать, чтобы для разностной схемы выполнялись аналоги таких законов сохранения. Разностные схемы, удовлетворяющие этому требованию, называются консервативными. Оказалось, что при одном и том же числе уравнений в дискретной задаче консервативные разностные схемы более правильно отражают поведение решения исходной разностной задачи, чем неконсервативные схемы.
Сходимость численного метода тесно связана с его корректностью.
Пусть исходная математическая задача поставлена корректно, т.е. ее решение существует, единственно и непрерывно зависит от входных данных. Тогда дискретная модель этой задачи должна быть построена таким образом, чтобы свойство корректности сохранялось. Следовательно, в понятие корректности численного метода включаются свойства однозначной разрешимости соответствующей системы уравнений и ее устойчивости. Под устойчивостью понимается непрерывная зависимость от входных данных.
Вторая группа требований, предъявляемых к численным методам, связана с возможностью реализации данной дискретной модели на данном компьютере, т.е. с возможностью получить численное решение за приемлемое время. Основным препятствием для реализации корректно поставленного алгоритма является ограниченный объем оперативной память
ЭВМ и ограниченное время счета. Компьютерно-ориентированные численные методы должны быть экономичными как по числу арифметических действий, так и по требуемому объему памяти.
Обычно сложные вычислительные задачи, возникающие при исследовании физических и технических проблем, разбиваются на ряд элементарных. Многие элементарные задачи являются несложными, они хорошо изучены, для них уже разработаны методы численного решения и имеются стандартные программы решения их на ЭВМ.
Целью занятий в осеннем семестре является знакомство студентов с методологией построения и исследования основных численных методов алгебры и математического анализа и проблемами, возникающими при численном решении задач.

97
Лекция № 2. Классификация погрешностей. Абсолютная и относительная погрешности числа и функции. Прямая и обратная задачи теории погрешностей. Неустойчивые алгоритмы.
Особенности машинной арифметики.

2.1. Классификация погрешностей
При численном решении математических и прикладных задач почти неизбежно появление на том или ином этапе погрешностей. Погрешностью называют отклонение приближенного решения от истинного решения.
Различают следующие типы погрешностей.
1. Неустранимая погрешность. Она связана с приближенным характером исходной содержательной модели, а также ее математического описания, в частности, с невозможностью учесть все факторы в процессе изучения моделируемого явления. Она также связана с тем, что параметрами математической модели служат обычно приближенные величины из-за принципиальной невозможности выполнения абсолютно точных измерений.
Для вычислителя погрешность математической модели следует считать
неустранимой (безусловной), хотя постановщик задачи иногда может ее изменить.
2. Погрешность метода. Это погрешность, связанная со способом решения поставленной математической задачи и появляющаяся в результате подмены исходной математической модели другой или конечной последовательностью других, например, линейных моделей. При создании численных методов закладывается возможность отслеживания таких погрешностей и доведения их до сколь угодно малого уровня. Отсюда естественно отношение к погрешности метода как к устранимой (или условной).
3. Вычислительная погрешность (погрешность действий). Этот тип погрешности обусловлен необходимостью выполнять арифметические операции над числами, усеченными до количества разрядов, зависящего от применяемой вычислительной техники (если, разумеется, не используются специальные программные средства, реализующие, например, арифметику рациональных чисел), т.е. вычислительная погрешность обусловлена округлениями.
Все три описанных типа погрешностей в сумме дают полную
погрешность результата решения задачи. Поскольку первый тип погрешностей не находится в пределах компетенции вычислителя, то для вычислителя он служит лишь ориентиром точности, с которой следует рассчитывать математическую модель. Нет смысла решать задачу существенно точнее, чем это диктуется неопределенностью исходных данных. Таким образом, погрешность метода подчиняют погрешности

98
задачи. Наконец, при выводе оценок погрешностей численных методов обычно исходят из предположения, что все операции над числами выполняются точно. Это означает, что погрешность округлений не должна существенно отражаться на результатах реализации методов, т.е. должна подчиняться погрешности метода. Влияние погрешностей округлений не следует упускать из вида ни на стадии отбора и алгоритмизации численных методов, ни при выборе вычислительных и программных средств, ни при выполнении отдельных действий и вычислении значений функций.
Пример. Пусть требуется вычислить площадь фигуры, ограниченной некоторой кривой, отрезками прямых и осью ординат.

Рис. 1. Площадь фигуры с криволинейной границей
Пусть S – это истинное значение площади рассматриваемой фигуры. В качестве математической модели для вычисления площади возьмем интеграл
∫
b
a
dx
x
f
)
(
. Неточность в этом выражении заложена в числах a и
b
и в функции
)
(x
f
y
=
, которая аппроксимирует криволинейную границу области. Пусть
∫
=
b
a
dx
x
f
S
)
(
1
– истинное значение интеграла. Тогда разность
1
S
S
−
и будет неустранимой погрешностью. Для вычисления интеграла применим численный метод, допустим некоторую интегральную сумму
∑
=
∆
n
i
i
i
x
x
f
1
)
(
. Пусть
2
S – истинное значение суммы. Разность
2 1
S
S
−
– это погрешность метода. Пусть, наконец,
3
S – тот результат, который получился после вычисления суммы. Из-за округлений получим величину, вообще говоря, отличающуюся от
2
S . Разность
3 2
S
S
−
– это вычислительная погрешность. Сумма трех указанных погрешностей, которая равна разности
3
S
S
−
, т.е. разности между истинным значением площади (неизвестным нам) и тем значением, которое мы выдаем в качестве решения задачи, и есть полная погрешность.
Некоторые алгоритмы весьма чувствительны к ошибкам округлений.
При счете по таким алгоритмам небольшая погрешность, допущенная на

99
каком-либо его шаге, может сильно нарастать и в результате получится весьма большая вычислительная погрешность. Такие алгоритмы называют

Каталог: ebibl -> umkd
umkd -> Глоссарий
umkd -> Разработка технологической документации