Введение в вычислительную математику

А.И. Лобанов И.Б. Петров






Введение в вычислительную математику












^ИНТУИТ
  / НАЦИОНАЛЬНЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ

С.ИНТУ ИТ

    У НАЦИОНАЛЬНЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ


Введение в вычислительную математику
2-е издание, исправленное

Петров И.Б.
Лобанов А.И.



Национальный Открытый Университет “ИНТУИТ”
2016


2

Введение в вычислительную математику/ И.Б. Петров, А.И. Лобанов - М.: Национальный Открытый Университет “ИНТУИТ”, 2016
В курсе лекций рассматриваются основные понятия и методы вычислительной математики.
Курс содержит как лекции, посвященные классическим численным методам анализа и линейной алгебры, так и решению дифференциальных уравнений.
(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Петров И.Б., Лобанов А.И., 2007-2016

3

Предисловие

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

За основу данного курса были взяты курсы вычислительной математики, которые в течение ряда лет читались студентам факультетов общей и прикладной физики, молекулярной и биологической физики, проблем физики и энергетики МФТИ. Слушатели этих курсов — не профессионалы-вычислители, а исследователи, специалисты в предметной области. Но логика современного развития науки привела к тому, что успех исследования во многом определяется эффективностью применения вычислительной техники и численных методов. В этой связи авторы посчитали необходимым дать студентам представление и о сравнительно современных численных методах. В силу быстрых изменений, происходящих сейчас в вычислительной математике, издать курс, на 100 процентов удовлетворяющий потребностям сегодняшнего дня, просто невозможно.

В курс включены идеи, методы, разделы, которые не являются обязательными и при первом прочтении могут быть опущены. Отметим, что термин “лекция” несколько условен. В данный курс входит годовой курс, число лекций в году составляет 30-33. В этом курсе 19 лекций, в силу того, что под лекцией здесь понимается тематический раздел, который может включать в себя материал нескольких реально читаемых лекций.

Большинство лекций курса (все основные и некоторые необязательные) снабжены задачами для разборов на семинарских занятиях и для самостоятельного решения на компьютере с использованием либо пакетов программ, либо оригинальных программ, составленных самими обучающимися. По мнению авторов, без самостоятельной реализации основных алгоритмов и простых вычислительных процедур невозможно глубокое понимание предмета. В конце каждой лекции приведен список литературы — это источники, которыми пользовались авторы при написании курса, и специальная литература, более подробно освещающая те или иные разделы. Списки литературы не претендуют на полноту, а лишь отражают вкусы и научные пристрастия авторов.

Все замечания можно направлять по электронной почте по адресам alexey@crec.mipt.ru или petrov@mipt.ru.

Авторы выражают свою искреннюю благодарность всем коллегам по кафедре вычислительной математики МФТИ за внимание и помощь в работе, первому заведующему кафедрой академику О.М.Белоцерковскому за доброжелательную поддержку. Особая благодарность В.С.Рябенькому, Р.П.Федоренко, А.С.Холодову, учителям авторов, которые передали им свои знания и любовь к предмету. Доценты


4

Е.Н.Аристова, О.А.Пыркова, Т.К.Старожилова и старший преподаватель В.Д.Иванов прочли части книги в рукописи и высказали ряд конструктивных замечаний и предложений. Много сил и энергии потратили Е.А.Евсюкова, Д.В.Кибардина и Е.Р.Павлюкова при технической подготовке рукописи. Авторы также благодарны Ж.И.Утюшевой и М.С.Гриневой за предоставленные конспекты лекций.

5

                Предмет вычислительной математики. Обусловленность задачи, устойчивость алгоритма, погрешности вычислений. Задача численного дифференцирования




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

Предмет вычислительной математики. Обусловленность задачи, устойчивость алгоритма, погрешности вычислений. Задача численного дифференцирования

Первое применение вычислительных методов принадлежит древним египтянам, которые умели вычислять диагональ квадрата за конечное количество действий. Они также могли находить квадратный корень из 2, скорее всего, с помощью алгоритма, в дальнейшем получившего название формулы Герона, а еще позднее — метода Ньютона:

Ufc+L =        , U.Q =: a.
      ■“ \   uJc /

С именем среднеазиатского врача, философа и математика Аль-Хорезми связано понятие алгоритма. Разработкой вычислительных методов занимались Л.Эйлер, которому принадлежит, по-видимому, первый численный метод для решения обыкновенных дифференциальных уравнений, И.Ньютон, О.Л.Коши, Ж.Л.Лагранж, А.М.Лежандр, П.С.Лаплас, А.Пуанкаре, П.Л.Чебышёв и многие другие известные математики. Решающую роль в развитии вычислительной математики как самостоятельной науки сыграли немецкий математик Карл Рунге и русский математик, механик и кораблестроитель А.Н.Крылов.

В наше время вычислительная математика получила значительный импульс в 1950-е годы, что было связано с развитием ядерной физики, механики полета, аэродинамики спускаемых космических аппаратов. В дальнейшем решались задачи, связанные не только с расчетами действия ядерного взрыва и обтеканием боеголовок стратегических ракет. Численные методы нашли свое применение в таких областях как динамика атмосферы, термогидрография, физика плазмы, механика горных пород и ледников, синергетика, биомеханика, теория оптимизации, математическая экономика и др. Наиболее наукоемки и требуют максимальных вычислительных ресурсов задачи физики, механики и электродинамики сплошных сред. К ним относятся системы уравнений в частных производных Эйлера, Лагранжа, Максвелла и др., кинетической теории газов (уравнения Власова, Берда), а также задачи многомерной оптимизации. Развитие многих вычислительных методов — заслуга ученых, неразрывно связанных с МФТИ. Среди них следует упомянуть академиков А.А. Дородницына, О.М.Белоцерковского, А.А.Самарского, членов-корреспондентов РАН А.С.Холодова,


6

Б.Н.Четверушкина, Ю.П.Попова, С.П.Курдюмова, профессоров В.С.Рябенького, Э.Э.Шноля, Р.П.Федоренко, Л.А.Чудова, В.Ф.Дьяченко, И.М.Гельфанда, Г.А.Тирского, А.П.Фаворского.

Вычислительная математика отличается от других математических дисциплин и обладает специфическими особенностями.

 1. Вычислительная математика имеет дело не только с непрерывными, но и с дискретными объектами. Так, вместо отрезка прямой часто рассматривается система точек ; };? ,,, вместо непрерывной функции f(x) — табличная функция
     | ■. 1 .., вместо первой производной — ее разностная аппроксимация, например, fk+i ~ fk хь+i -  '

    к =0 4- A, xfc+i > xk.

    Такие замены, естественно, порождают погрешности метода.

 2. В машинных вычислениях присутствуют числа с ограниченным количеством знаков после запятой из-за конечности длины мантиссы при представлении действительного числа в памяти ЭВМ. Другими словами, в вычислениях присутствует машинная погрешность (округления) Это приводит к вычислительным эффектам, неизвестным, например, в классической теории обыкновенных дифференциальных уравнений, уравнений математической физики или в математическом анализе.
 3. В вычислительной практике большое значение имеет обусловленность задачи, т.е. чувствительность ее решения к малым изменениям входных данных.
 4. В отличие от “классической” математики выбор вычислительного алгоритма влияет на результаты вычислений.
 5. Существенная черта численного метода — экономичность вычислительного алгоритма, т.е. минимизация числа элементарных операций при выполнении его на ЭВМ.
 6. Погрешности при численном решении задач делятся на две категории — неустранимые и устранимые. К первым относят погрешности, связанные с построением математической модели объекта и приближенным заданием входных данных, ко вторым — погрешности метода решения задачи и ошибки округления, которые являются источниками малых возмущений, вносимых в решение задачи.

Специфику машинных вычислений можно пояснить на нескольких элементарных примерах.

1.1. Обусловленность задачи

Пример 1.1. Вычислить все корни уравнения


7

z⁴ - 4z³ + 8z² - 16z + 15.9999999g = (z - 2)⁴ - 1СГ⁸ = 0.


Точное решение задачи легко найти:

        = iio⁻⁴,
rrL = 2, 01: z₂ = l₃99;x₃ ₄ = 2 ± 0, Oh.


Если компьютер работает при . ।  111 , то свободный член в исходном уравнении
будет округлен до 16,0 и, с точки зрения представления чисел с плавающей точкой, будет решаться уравнение (x-2)⁴= 0, т.е. x₁,₂,₃,₄ = 2, что, очевидно, неверно. В данном случае малые погрешности в задании свободного члена : ■ 111 привели, независимо от метода решения, к погрешности в решении : ■ 111 J

Пример 1.2. Решается задача Коши для обыкновенного дифференциального уравнения 2-го порядка:

 u''(t) = u(t), u(0) = 1, u'(0) = - 1.

Общее решение имеет вид

 u(t) = 0,5[u(0) + u'(0)]et + 0,5[u(0) - u'(0)]e⁻ t.

При заданных начальных данных точное решение задачи: u(x) = e⁻t, однако малая погрешность в их задании приведет к появлению члена , □*, который при больших значениях аргумента может существенно исказить решение.

Пример 1.3. Пусть необходимо найти решение обыкновенного дифференциального уравнения

1/ = Юи, и = и(£), u(t₍₎)=u₍b te[o,i].


Его решение:                   , однако значение u(t₀) известно лишь приближенно:
.■.,'...-:.■.., и на самом деле

Соответственно, разность u* - u будет и* — и =

Предположим, что необходимо гарантировать некоторую заданную точность вычислений / > о всюду на отрезке .   ¹ I Тогда должно выполняться условие





Очевидно, что


max |и* (t) — и(t) | = |u * (1) — и(1) | = |u₍* — зд |e¹ °'¹ '

8

Отсюда можно получить требования к точности задания начальных данных
3 п.р                 при t₀= 0.

Таким обазом, тебование к заданию точности начальных данных оказываются в e¹⁰ раз выше необходимой точности результата решения задачи. Это требование, скорее всего, окажется нереальным.

Решение оказывается очень чувствительным к заданию начальных данных. Такого рода задачи называются плохо обусловленными.

Пример 1.4. Решением системы линейных алгебраических уравнений (СЛАУ)

   и + Юи = 11
\ 100u+1001v= 11D1

является пара чисел {1, 1}.

Изменив правую часть системы на 0,01, получим возмущенную систему

 ' « + 10г = 11.01
\ 100u+lOOlv = 11D1

с решением {11.01; 0.00}, сильно отличающимся от решения невозмущенной системы. Эта система также плохо обусловлена.

Пример 1.5. Рассмотрим полином

 (x - 1)(x - 2)...(x - 20)=x²⁰ - 210x¹⁹ + ...,

корни которого Х1 = 1, Х2 = 2, ..., Х₂₀ = 20.

Положим, что коэффициент (-210) при x₁₉ увеличен на > 111 ⁷ В результате вычислений с 11-ю значащими цифрами получим совершенно иные корни:
Xi = 1,00:^2 = 2,00;жз = 3,00; .гц = 4, 00;zs = 5,00: ггц = 6,00: z? =
7,00: х* = В, 01; z₉ = 8,92: z₁₍₎ᵢₗₗ = 10,1=1=0, 644z;z₁₂ᵢ₁₃ = 11,8±1, 65i; z₁₄ⱼₗ₅ =
14, 0 ± 2, 52i;z₁Sᵢ₁t = 16,7 ± 2,81?: z₁₈ᵢₗg = 19, 5 ± 19, 4z:z’₂O = 20,8.
Причина значительного расхождения также заключается в плохой обусловленности задачи вычисления корней рассматриваемого выражения.

1.2. Влияние выбора вычислительного алгоритма на результаты вычислений


Пример 1.6. Пусть необходимо вычислить значение выражения


Избавившись от знаменателя, получаем . ч _   | ■" ■           " ■ _ц , _


9

Полагая


а)


2 « | = 1,4, и

в)




и рассматривая эти приближения как разные методы вычисления, получим следующие результаты:


V'"2 (у/2 - if (3 - 2л/2)" ⁹⁹ - ⁷⁰V'"2
7/5  0,0040960,008000 1
17/12 0,005233 0,004630 - 0,1(6)


Очевидно, что столь значительное различие в результатах вызвано влиянием ошибки округления в задании
Пример 1.7. Вычисление функции sin x с помощью ряда Тейлора.

Из курса математического анализа известно, что функция синус представляется своим рядом Тейлора

sin гг = х — зр + — 7Г + ■ ■ ■'

причем радиус сходимости ряда равен бесконечности — ряд сходится при любых значениях x.

Вычислим значения синуса при двух значениях аргумента. Пусть сначала
    и. •>•_! ;i.. ;i.' ■ Будем учитывать лишь члены ряда, большие, чем 10⁻ ⁴. Выполнив вычисления с четырьмя значащими цифрами, получим sin (0.5236) = 0.5000, что соответствует принятой точности.

Пусть теперь .......... 1711 ■ Если вычисления по данной формуле проводить с
восемью значащими цифрами, то получим абсурдный результат: . . .■ 7' и.. I (учитывались члены ряда, большие, чем 10⁻⁸ ).

Разумеется, выходом из создавшейся ситуации может быть использование формул приведения.

Пример 1.8. Вычисление функции ex с помощью ряда Тейлора.

Из курса математического анализа известно, что экспонента представляется своим рядом Тейлора

   — 1 + 37 + туг + тт,-h . . . ,


10