корнюшин.численные методы

ДАЛЬНЕВОСТОЧНЫЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ТИХООКЕАНСКИЙ ИНСТИТУТ ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ И ТЕХНОЛОГИЙ

П. Н. Корнюшин

ЧИСЛЕННЫЕ

МЕТОДЫ

© Издательство Дальневосточного университета 2002

ВЛАДИВОСТОК

2002 г.

2

СОДЕРЖАНИЕ

1.1.2.6. Разностное уравнение второго порядка с переменными коэффициентами. Задача Коши и краевая

4

Аннотация

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

Пособие предназначено для студентов вузов, изучающих основы вычислительной математики.

Рецензия на учебное пособие П.Н. Корнюшина «Численные методы»

Написать учебное пособие по численным методам при наличии трудов таких классиков вычислительной математики, как Н.С. Бахвалов, И.С. Березин, Н.П. Жидков, А.А. Самарский и др.

– задача очень неблагодарная, поскольку все основные методы вычислений описаны с различными уровнями подробности. Правда, пока еще не встречалось учебного пособия, предназначенного для дистанционного обучения. К тому же, данное учебное пособие предназначено для студентов, только начинающих освоение элементов вычислительной математики. Поэтому перед автором стояла непростая задача при сохранении относительной строгости изложения сделать материал в достаточной мере доступным для понимания. Поэтому, по-видимому, не следует требовать в каждом конкретном случае строгости при доказательстве теорем существования и единственности, если задача изложена на понятном качественном уровне.

Цель, поставленная автором пособия, на мой взгляд, достигнута. Пособие написано достаточно понятным языком. Изложены Основные методы вычислений. К тому же, по сравнению с традиционным содержанием, в курс включены разделы линейного программирования, что особенно важно для студентов экономических специальностей.

В целом, издание учебного пособия, в особенности в электронном виде (с учетом дефицита именно такой продукции), – необходимо и актуально.

Методические указания для студентов

1)Консультации можно получить по адресу: г. Владивосток, ул. Суханова 8, ДВГУ, ауд. 76 или по электронной почте: korn@ifit.phys.dvgu.ru.

2)Форма аттестации по курсу – компьютерное тестирование в соответствии с прилагаемыми тестами.

3)Нормы аттестации: сдача каждого из 4-х тестирований, соответствующих 4-м модулям, не менее чем на «удовлетворительно».

5

Модуль 1. Введение. Разностные уравнения

1.0. Введение

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

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

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

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

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

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

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

Следует отметить, что вычислительный эксперимент – это, как правило, не разовый счет по стандартным формулам, а, прежде всего, расчет серии вариантов для различных математических моделей.

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

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

6

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

При решении задачи на компьютере мы всегда получаем не точное решение исходной задачи, а некоторое приближенное решение. Чем же обусловлена возникающая погрешность? Можно выделить три основные причины возникновения погрешности при численном решении исходной математической задачи. Прежде всего, входные данные исходной задачи (начальные и граничные условия, коэффициенты и правые части уравнений) всегда задаются с некоторой погрешностью. Погрешность численного метода, обусловленную неточным заданием входных данных, принято называть неустранимой погрешностью. Далее, при замене исходной задачи дискретной задачей возникает погрешность, называемая погрешностью дискретизации или погрешностью метода. Например, заменяя производную u’(x) разностным отношением (u(x+∆x)- u(x))/∆x, мы допускаем погрешность дискретизации, имеющую при ∆x →0 порядок ∆x. Наконец, конечная разрядность чисел, представляемых в компьютере, приводит к погрешностям округления, которые могут нарастать в процессе вычислений. Естественно требовать, чтобы погрешности в задании начальной информации и погрешность, возникающая в результате дискретизации, были согласованы с погрешностью решения на компьютере дискретной задачи.

Сказанное означает, что основное требование, предъявляемое к вычислительному алгоритму, – это требование точности. Оно означает, что вычислительный алгоритм должен давать решение исходной задачи с заданной точностью ε >0 за конечное число Q(ε) действий. Алгоритм должен быть реализуемым, т.е. обеспечивать решение задачи за допустимое машинное время или, в силу конечной скорости вычислений на компьютере, – за допустимое число действий. Для большинства алгоритмов время решения задачи (объем вычислений) Q(ε) возрастает при повышении точности, т.е. при уменьшении ε. Конечно, можно задать ε настолько малым, что время счета задачи станет недопустимо большим. Важно знать, что алгоритм дает принципиальную возможность получить решение задачи с любой точностью. Однако на практике величину ε выбирают, учитывая требование точности и возможность реализуемости алгоритма на данном компьютере. Для каждой задачи, алгоритма и машины есть свое характерное значение ε.

Естественно добиваться, чтобы число действий (и тем самым машинное время решения задачи) Q(ε) было минимальным для данной задачи. Для любой задачи можно предложить много алгоритмов, дающих одинаковую по порядку (при ε→0) точность ε>0, но за разное число действий Q(ε). Среди этих эквивалентных по порядку точности алгоритмов надо выбрать тот, который дает решение с затратой наименьшего машинного времени (числа действий Q(ε)). Такие алгоритмы будем называть оптимальными.

Остановимся еще на одном требовании, предъявляемом к вычислительному алгоритму, а именно – требовании отсутствия аварийного останова (авоста) компьютера в процессе вычислений. Следует иметь в виду, что компьютер оперирует с числами, имеющими конечное число значащих цифр и принадлежащих (по модулю) не всей числовой оси, а некоторому интервалу (М0,М∞), М0>0, М∞<∞, где М0 – машинный нуль, М∞ – машинная бесконечность. Если условие │М│<М∞ в процессе вычислений нарушается, то происходит аварийный останов вследствие переполнения разрядной сетки, и вычисления прекращаются. Возможность авоста зависит как от алгоритма, так и от исходной задачи.

Если решение исходной задачи выражается через очень большие (очень малые) числа │М│>М∞ (│М│<М0), то, как правило, путем изменения масштабов можно привести задачу к виду, содержащему только величины, принадлежащие (по модулю) заданному интервалу (М0,М∞). Часто возможность авоста может быть устранена путем изменения порядка действий. Поясним это на простом примере.

Пример 1. Пусть М∞=10р, М0=10-р, р=2n, n – целое число. Требуется вычислить

произведение чисел 10p/2,10p/4,10-p/2,103p/4,10-3p/4.

1-й способ. Перенумеруем числа в порядке убывания: q1=103p/4, q2=10p/2, q3=10p/4, q4=10-p/2,

q5=10-3p/4 и образуем произведения Sk+1=Skqk+1, S1=q1. Тогда уже на первом шаге мы получим авост, т.к. S2=q1q2=105p/4>M∞.

2-й способ. Перенумеруем числа в порядке возрастания: q1=10-3p/4, q2=10-p/2, q3=10p/4, q4=10p/2, q5=103p/4. В этом случае мы получим на первом шаге S2 = q1q2 =10-5p/4<M0, т.е. S2 –

машинный нуль; нулю равны и все последующие произведения S3, S4, S5; таким образом, здесь происходит полная потеря точности.

7

3-й способ. Перемешаем эти числа, полагая, q1=10-3p/4, q2=10p/2, q3=103p/4, q4=10-p/2, q5=10p/4.

Тогда последовательно найдем: S2=q1q2=10-p/4, S3=S2q3=10p/2, S4=S3q4=100, S5=S4q5=10p/4, т.е. в

процессе вычислений не появляются числа, большие 10p/2 и меньшие 10-p/4. Такой алгоритм является безавостным.

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

Пример 2. Пусть требуется найти yi (0<i ≤i0) по формуле yi+1=yi+d (i ≥0) при заданных y0, d. Предположим, что при вычислении yi внесена погрешность (например, погрешность

округления), имеющая величину δi, т.е. вместо точного значения yi получено приближенное

промежуточном шаге, не увеличивается в процессе вычислений. Алгоритм устойчив.

Пример 3. Рассмотрим уравнение yi+1=qyi (i≥0, y0 и q заданы). Пусть, как и в примере 2,

вычислении yi+1, связана с погрешностью δi уравнением δi+1=qδi, i=0,1,2,…. Следовательно, если q >1, то в процессе вычислений абсолютное значение погрешности будет возрастать (алгоритм

неустойчив). Если же q ≤1, то погрешность не возрастает, т.е. алгоритм устойчив.

Неустойчивость обычно связывают со свойством экспоненциального нарастания ошибки округления. Если же погрешность округления нарастает по степенному закону при переходе от одной операции к другой («от шага к шагу»), то алгоритм считают условно устойчивым (устойчивым при некоторых ограничениях на объем вычислений и требуемую точность). Процесс вычислений можно трактовать так: при переходе от шага к шагу происходит искажение (за счет погрешностей округления) последних значащих цифр (от последних значащих цифр справа налево движется «волна погрешности округления»). Нам нужно обычно сохранить верными несколько первых значащих цифр (4-5 знаков), и поэтому вычисления должны быть закончены до того, как до них дойдет «волна погрешности округления». Если погрешность округления ε0 нарастает от шага к шагу по экспоненциальному закону, то это приводит, как правило, к авосту на

ограничение на число уравнений i≤i0. Так, при k0=12, k=6 имеем i≤106/n, так что i≤103 при n=2. Ясно, что можно указать такое большое n, что допустимое число уравнений i0 очень мало. Однако на практике обычно встречаются случаи небольшого n.

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

8

случае задача поставлена корректно (задача корректна). Это значит, что 1) задача разрешима при любых допустимых входных данных; 2) имеется единственное решение; 3) решение задачи непрерывно зависит от входных данных (малому изменению входных данных соответствует малое изменение решения) – иными словами, задача устойчива. Во втором случае задача поставлена некорректно (задача некорректна). Такой вариант возникает, если, например, решение задачи неустойчиво относительно входных данных (малому изменению входных данных может соответствовать большое изменение решения).

Примером корректной задачи может служить задача интегрирования, а примером некорректной задачи – задача дифференцирования.

интеграла J воспользуемся квадратурной формулой:

δu' c =N≥1/ε. Таким образом, малому изменению O(ε) в С функции u(x) соответствует большое

изменение O(1/ε) в С ее производной. Поэтому численное дифференцирование некорректно. Чтобы найти приближенное значение производной по формуле разностной производной с

некоторой точностью ε>0 при условии, что функция задана с погрешностью δi ( δi ≤δ0 ),

необходимо выполнение условий согласования ε, δ0 и шага h сетки, например, вида ε≥k δ0

(k=const>0 не зависит от h, δ0, причем шаг сетки ограничен как снизу, так и сверху. Таким образом, достижимая точность численного дифференцирования лимитируется точностью задания самой функции.

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

Численные методы дают приближенное решение задачи. Это значит, что вместо точного решения u (функции или функционала) некоторой задачи мы находим решение y другой задачи, близкое в некотором смысле к искомому. Как уже указывалось, основная идея всех методов – дискретизация или аппроксимация (замена, приближение) исходной задачи другой задачей, более удобной для решения на компьютере, причем решение аппроксимирующей задачи зависит от некоторых параметров, управляя которыми можно определить решение с требуемой точностью. Например, в задаче численного интегрирования такими параметрами являются узлы и веса квадратурной формулы. Далее, решение дискретной задачи является элементом конечномерного пространства. Остановимся на этом подробнее.

Рассмотрим, например, дискретизацию пространства H={f(x)} функций f(x) непрерывного

_

аргумента x [a,b]. На отрезке a ≤ x ≤ b введем конечное множество точек ω ={xi, i=0,1,…,N,

_

x0=a, xN=b, xi<xi+1}, которое назовем сеткой. Точки xi будем называть узлами сетки ω . Множество

9

_

ω без узлов x0 и xN будем обозначать ω. Если расстояние hi=xi-xi-1 между соседними узлами постоянно (не зависит от i), hi=h для всех i=1, 2,…, N, то сетку ω называют равномерной (с шагом h), в противном случае – неравномерной. Вместо функции f(x), определенной для всех x [a,b], будем рассматривать сеточную функцию yi=f(xi) целочисленного аргумента i (i=0, 1,…, N) или

_

узла xi сетки ω , а H={f(x), x [a,b]} заменим конечномерным (размерности N+1) пространством HN+1={yi, 0≤i≤N} сеточных функций. Очевидно, что сеточную функцию yi=f(xi) можно рассматривать как вектор y=(y0, y1,…, yN).

Можно провести также дискретизацию и пространства функций f(x) многих переменных, когда x=(x1, x2,…, xp) – точка р-мерного евклидового пространства (р>1). Так, на плоскости (x1, x2) можно ввести сетку ω={xi=(i1h1, i2h2), i1, i2 =0, ±1,±2,...} как множество точек (узлов) пересечения

перпендикулярных прямых x1(i1 ) = i1h1 , x2(i2 ) = i2 h2 , h1 > 0, h2 > 0, i1 , i2 = 0,±1,±2,... , где h1 и h2 – шаги сетки по направлениям x1 и x2 соответственно. Сетка ω, очевидно, равномерна по каждому из переменных в отдельности. Вместо функции f(x)=f(x1, x2) будем рассматривать сеточную функцию

_

yi1i2 = f (i1h1 , i2 h2 ) . Если сетка ω содержит только те узлы, которые принадлежат

прямоугольнику (0≤x1≤l1, 0≤x2≤l2), так что h1=l1/N1, h2=l2/N2, то сетка имеет конечное число N=(N1+1)(N2+1) узлов, а пространство HN сеточных функций yi= yi1i2 является конечномерным.

Мы всюду рассматриваем только конечномерное пространство сеточных функций. Заменяя пространство H={f(x)} функций непрерывного аргумента и исходную задачу пространством H сеточных функций и дискретной аппроксимацией исходной задачи, мы должны быть уверены, что будем лучше приближаться к решению исходной задачи при увеличении числа узлов. Оценка качества приближения и выбор способа аппроксимации – главная задача теории численных методов.

Основное содержание курса в той или иной степени связано с применением разностных методов для решения дифференциальных уравнений. Выделим два главных вопроса:

1)получение дискретной (разностной) аппроксимации дифференциальных уравнений и исследование получающихся при этом разностных уравнений;

2)решение разностных уравнений.

При получении дискретной аппроксимации (разностные схемы) важную роль играет общее требование, чтобы разностная схема как можно лучше приближала (моделировала) основные свойства исходного дифференциального уравнения. Такие разностные схемы можно получать, например, при помощи вариационных принципов и интегральных соотношений. Оценка точности разностной схемы сводится к изучению погрешности аппроксимации и устойчивости схемы. Изучение устойчивости – центральный вопрос теории численных методов и ему уделяется большое внимание в данном курсе. Алгоритмы для сложных задач можно представить как последовательность (цепочку) простых алгоритмов (модулей). Поэтому многие принципиальные вопросы теории числовых методов можно выяснить на простых алгоритмах.

Впервой главе рассматриваются одномерные (зависящие от одного целочисленного аргумента) разностные уравнения.

Вторая глава посвящена численному решению алгебраических и трансцендентных уравнений.

Втретьей главе излагаются основы теории интерполирования.

Четвертая глава содержит основные методы численного интегрирования.

В пятой главе рассматривается численное решение систем линейных алгебраических уравнений.

Шестая глава дает основные сведения классификации, постановки и решения задач линейного программирования.

10

1.1.Разностные уравнения

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

1.1.1.Сеточные функции

1.1.1.1.Сеточные функции и действия над ними

Как уже упоминалось, в приближенных методах обычно функции непрерывного аргумента заменяются функциями дискретного аргумента – сеточными функциями. Сеточную функцию можно рассматривать как функцию целочисленного аргумента:

y(i)=yi, i=0, ± 1, ± 2,….

Для y(i) можно ввести операции, являющиеся дискретным (разностным) аналогом операций дифференцирования и интегрирования.

Аналогом первой производной являются разности первого порядка:

∆yi=yi+1-yi – правая разность;yi=yi-yi-1 – левая разность;

δyi= 12 (∆yi+ yi)= 12 (yi+1-yi-1) – центральная разность;

следует заметить, что ∆yi= yi+1.

Далее можно определить разности второго порядка:

∆2yi=∆(∆yi)=∆(yi+1-yi)=yi+2-2yi+1+yi,

∆ yi=∆(yi-yi-1)=(yi+1-yi)-(yi-yi-1)=yi+1-2yi+yi-1,

так что ∆2yi=∆ yi+1.

Аналогично определяется разность m-го порядка: ∆myi=∆(∆m-1yi), содержащая значения yi, yi+1,…,yi+m. Очевидно, что

1.1.1.2. Разностные аналоги формул дифференцирования произведения и интегрирования по частям

Пусть yi, vi – произвольные функции целочисленного аргумента. Тогда справедливы формулы:

которые проверяются непосредственно. Например,

∆(yivi)=yi+1vi+1-yivi; yi∆vi+vi+1∆yi=yi(vi+1-vi)+vi+1(yi+1-yi)=yi+1vi+1-yivi=∆(yivi).

При выводе формулы для (yivi) достаточно учесть, что (yivi)=∆(yi-1vi-1).

Формулы (1), (2) представляют собой аналоги формулы дифференцирования произведения

(y(x)v(x))'=yv'+vy'.

Аналогом формулы интегрирования по частям является формула суммирования по частям:

которую записывают также в виде