- •Бояршинов, М.Г.
- •1. ЧИСЛЕННЫЕ МЕТОДЫ АЛГЕБРЫ
- •1.1. Системы линейных алгебраических уравнений
- •1.2. Нелинейные уравнения
- •1.3. Аппроксимация функций
- •1.4. Собственные значения и собственные векторы
- •2. ЧИСЛЕННЫЕ МЕТОДЫ АНАЛИЗА
- •2.1. Численное дифференцирование
- •2.2. Численное интегрирование
- •3.2. Граничные задачи
- •4. ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ
- •4.1. Системы линейных алгебраических уравнений
- •4.2. Нелинейные уравнения
- •4.3. Аппроксимация функции
- •4.4. Собственные значения и собственные векторы
- •4.7. Задачи Коши
- •4.8. Граничные задачи
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Министерство образования и науки российской Федерации
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ПЕРМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
М. Г. Боярш инов
Численные методы
Часть 4
Допущено Министерством образования и науки Российской Федерации в качестве учебного пособия для студентов вузов, обучающихся по специальностям:
«Автоматизированные системы обработки информации и управления» (220200), «Вычислительные машины, комплексы, системы и сети» (220100)
Пермь 2006
УДК 681.3 Б86,
Рецензенты:
доктор физико-математических наук, профессор, заведующий кафедрой высшей математики МИРЭА
Ю.И. Худак\
доктор физико-математических наук, профессор, заместитель директора Института механики сплошных сред УрО РАН по науке
А.А. Роговой; кандидат физико-математических наук,
доцент Пермского государственного технического университета
Н.Д. Няшина
Бояршинов, М.Г.
Б86 Численные методы: учеб, пособие / М.Г. Бояршинов; Перм. гос. техн. ун-т. - Пермь, 2006. - Ч. 4. - 162 с.
ISBN 5-98975-080-3
Учебное пособие написано на основе курсов лекций, практических занятий и ла бораторных работ для студентов инженерных специальностей Пермского государст венного технического университета, изучающих вычислительные методы и приме няющих их для решения прикладных задач.
Рассматриваются основные положения теории решения систем линейных алгеб раических уравнений прямыми и итерационными методами, нелинейных уравнений, построения полиномов Лагранжа и Ньютона, использования метода наименьших квад ратов, нахождения собственных чисел и векторов, численного интегрирования и диф ференцирования, решения задач Коши и граничных задач сеточными методами и с ис пользованием метода Галеркина.
Излагаются алгоритмы решения прикладных задач с использованием вычисли тельной техники, приемы оценки погрешностей получаемых решений, возможные спо собы отображения результатов расчетов. По каждой рассматриваемой теме приведены задания для самостоятельной работы студентов.
Предназначено для студентов и аспирантов Пермского государственного техниче ского университета, специалистов, занимающихся построением моделей механических систем и процессов. Может быть использовано при проведении факультативных заня тий по компьютерному моделированию.
|
УДК 681.3 |
ISBN 5-98975-080-3 |
© Пермский государственный |
|
технический университет, 2006 |
|
© Бояршинов М.Г., 2006 |
Введение..................................................................................................................... |
5 |
|
1. Численные методы алгебры.............................................................................. |
10 |
|
1.1. Системы линейных алгебраических уравнений....................................... |
10 |
|
1.1.1. Метод Гаусса........................................................................................... |
10 |
|
1.1.2. Метод квадратного корня..................................................................... |
19 |
|
11.3. Метод Якоби.......................................................................................... |
22 |
|
11.4. Метод Зейделя........................................................................................ |
24 |
|
1.2. Нелинейные уравнения............................................................................... |
27 |
|
12.1. Метод половинного деления (дихотомия)......................................... |
27 |
|
12.2. Метод простых итераций...................................................................... |
30 |
|
1.2.3. Метод Ньютона...................................................................................... |
32 |
|
1.3. Аппроксимация функций............................................................................ |
36 |
|
13.1. Интерполяционный многочлен Ньютона........................................... |
36 |
|
13.2. Интерполяционный многочлен Лагранжа......................................... |
42 |
|
13.3. Метод наименьших квадратов............................................................. |
44 |
|
1- |
3.4. Наилучшее приближение в гильбертовом пространстве ............. |
47 |
1.4. Собственные значения и собственные векторы....................................... |
51 |
|
2. Численные методы анализа............................................................................... |
57 |
|
2.1. Численное дифференцирование................................................................. |
57 |
|
2.1.1. Разностный аналог первой производной......................................... |
58 |
|
2 1.2. Разностный аналог второй производной............................................ |
61 |
|
2.2. Численное интегрирование......................................................................... |
63 |
|
2 2.1. Формула прямоугольников................................................................... |
63 |
|
2- |
2.2. Формула трапеций ............................................................................. |
67 |
2- |
2.3. Формула парабол (Симпсона) .......................................................... |
69 |
3. Численные методы решения обыкновенных дифференциальных |
|
|
уравнений |
.......................................................................................................................... |
72 |
3 1- Задачи Коши.................................................................................................. |
72 |
|
3 1.1. .........................................................................................Метод Эйлера |
72 |
|
3 1.2. ......................................................Метод Рунге - Кутты 2-го порядка |
76 |
|
3.1.3. .....................................................Метод Рунге - Куггы 3-го порядка |
79 |
|
3- ..................................................1.4. Метод Рунге - Кутты 4-го порядка |
82 |
|
3-1.5. ........................................................................................Метод Адамса |
85 |
|
3 2. Граничные ........................................................................................задачи |
89 |
|
3 2.1. ..................................................................................Разностный метод |
89 |
|
3*2.2. .................................................................................Метод пристрелки |
95 |
|
3 2.3. ...................................................................................Метод Галеркина |
99 |
|
3*2.4. ...........................................................Метод наименьших квадратов |
104 |
|
4. Задация ..................................................для самостоятельного выполнения |
111 |
|
4.1. Системы .....................................линейных алгебраических уравнений |
111 |
|
4.2. Нелинейные ..............................................................................уравнения |
111 |
|
4.3. Аппроксимация ..........................................................................функции |
111 |
4.4. Собственные значения и собственные векторы..................................... |
144 |
4.5. Численное дифференцирование................................................................ |
154 |
4.6. Численное интегрирование........................................................................ |
155 |
4.7. Задачи Коши................................................................................................. |
156 |
4.8. Граничные задачи........................................................................................ |
158 |
4.8.1. Разностный метод.................................................................................. |
158 |
4.8.2. Метод пристрелки................................................................................ |
158 |
4.8.3. Метод Галеркина и метод наименьших квадратов.......................... |
158 |
Библиографический список.................................................................................. |
161 |
Учебное пособие предназначено для студентов, выполняющих вычисли тельные работы при изучении численных методов, расчетные работы во время практикумов по вычислительной математике, а также самостоятельно прово дящих исследования, связанные с вычислительными экспериментами при ре шении прикладных задач математики, механики, физики, химии, электротех ники, геологии и других дисциплин.
Первая глава 4-й части пособия «Численные методы» посвящена методам решения систем линейных алгебраических уравнений прямыми (Гаусса, квад ратного корня) и итерационными (Якоби, Зейделя) методами, нелинейных уравнений (методы Ньютона, половинного деления, простых итераций), ап проксимации функций (полиномы Ньютона, Лагранжа, методы наименьших квадратов, наилучшего приближения). В качестве обобщающего задания рас сматривается алгебраическая задача на собственные значения. Это задание по зволяет логично объединить предварительно изученные численные методы ал гебры для решения актуальной инженерной проблемы - поиска собственных значений и собственных векторов квадратной матрицы. При наличии возмож ности, вышеуказанная задача может быть выделена в самостоятельную курсо вую работу. Основное внимание при выполнении вычислительных работ в этой части пособия уделяется получению оценок погрешности численных решений, исследованию сходимости (расходимости) последовательностей получаемых решений при выполнении итерационных процедур, оценке эффективности вы числительных алгоритмов и программ.
Во второй главе рассматриваются способы построения разностных анало гов производных первого и второго порядков, а также вычисление приближен ных значений определенных интегралов методами прямоугольников, трапеций и парабол. Здесь одним из главных вопросов является теоретическая оценка порядка погрешности аппроксимации выбранной вычислительной схемой ис ходного дифференциального или интегрального соотношения. Рассматривают ся способы оценки погрешности численного результата с использованием по следовательности сгущающихся разностных сеток.
В третьей главе пособия численные методы используются для построения решений обыкновенных дифференциальных уравнений в задачах Коши (мето ды Эйлера, Рунге - Кутты, Адамса) и граничных задачах (методы пристрелки, сеточный, Галеркина, наименьших квадратов). Основная идея решения диффе ренциальных уравнений численными методами заключается, как правило, в сведении решения исходной дифференциальной задачи к решению систем ал гебраических (линейных или нелинейных) уравнений. При этом, естественно, возникает вопрос о решении получаемых систем алгебраических уравнений одним из изученных ранее методов. Как и в предыдущей главе, значительное внимание уделяется оценке погрешности аппроксимации разностной схемой исходного дифференциального уравнения, позволяющей судить о степени аде кватности используемой сеточной модели исходной дифференциальной задаче.
Погрешность получаемых численных решений дифференциальных уравнений анализируется на последовательностях разностных сеток.
При выполнении вычислительных работ следует обратить особое внима ние на оформление результатов вычислений в отчете. Образец титульного лис та отчета по выполнению вычислительных работ представлен на рис. В.1.
Федеральное агентство по образованию Пермский государственный технический университет
Кафедра вычислительной математики и механики
ЛАБОРАТОРНАЯ РАБОТА № 2
Решение нелинейного уравнения методом Ньютона
Выполнил:
студент гр. КМ-04 П.С. Иванов
Проверил:
профессор каф. ВММ М.Г Бояршинов
Пермь 2006
Рис. В.1. Образец титульного листа отчета по лабораторной работе
Отчет должен в обязательном порядке содержать:
1.Постановку задачи.
2.Краткое описание численного метода (при возможности - с графиче
ской иллюстрацией) и проверку условий его применимости.
3.Подробное описание алгоритма получения численного решения.
4.Оценку погрешности 5Лполучаемого численного решения. Как правило, для этого используется чебышёвская норма отклонения л-го приближения чис ленного решения уп{х) от точного решения у(х) на отрезке [а, Ь]9
^= ™ $}у(х) - уА х)\-
При отсутствии точного решения поставленной задачи погрешность полу чаемого результата оценивается с использованием чебышёвской нормы откло нения приближенного (численного) решения у„(х) от приближенного (числен ного) решения уп+\(х) на отрезке [<а, Ь]:
5 л = m aX ]|^1(x)->'„(x)|. |
|
|
|
Таблица В.1 |
|||||||
|
|
|
|
|
|
|
|
|
|
||
Пусть, |
например, |
получена |
Последовательность численных решений |
||||||||
последовательность у^х) |
числен |
у&х) дифференциальной задачи |
|||||||||
ных решений дифференциальной |
с различными сеточными шагами |
||||||||||
задачи с |
различными |
сеточными |
0,000 |
1,000 |
Уг(х,) |
Уз(*/) |
|||||
шагами (табл. В.1). Для получения |
1,000 |
1,000 |
|||||||||
оценки 5„ используются |
узловые |
0,125 |
|
|
0,875 |
||||||
значения |
двух |
приближений ис |
0,250 |
|
0,750 |
0,76563 |
|||||
комой функции (например, >^i(x) и |
0,375 |
|
|
0,66992 |
|||||||
УгОО) в общих узлах |
разностной |
|
|
||||||||
0,500 |
0,500 |
0,56250 |
0,58618 |
||||||||
сетки: 0; 0,5; 1; 1,5; 2. |
|
|
|
||||||||
|
|
|
0,625 |
|
|
0,51291 |
|||||
Разность |
узловых |
значений |
|
|
|||||||
0,750 |
|
0,42188 |
0,44879 |
||||||||
у2(х ) - У\{х) Дает набор соответст |
|
||||||||||
0,875 |
|
|
0,39269 |
||||||||
вующих |
значений: |
0; |
0,0625; |
|
|
||||||
1,000 |
0,250 |
0,31641 |
0,34361 |
||||||||
0,06641; 0,05298; 0,03761. Это по |
1,125 |
|
|
0,30066 |
|||||||
зволяет оценить погрешность д\ (в |
1,250 |
|
0,23731 |
0,26308 |
|||||||
соответствии |
с принятым |
выше |
1,375 |
|
|
0,23019 |
|||||
определением) значением, равным |
|
|
|||||||||
1,500 |
0,125 |
0,17798 |
0,20142 |
||||||||
0,06641. |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
1,625 |
|
|
0,17624 |
||
Затем для вычисления |
62 вы |
|
|
||||||||
1,750 |
|
0,13348 |
0,15421 |
||||||||
бираются |
узлы разностной |
сетки |
|
||||||||
1,875 |
|
|
0,13493 |
||||||||
0; 0,25; 0,5; |
0,75; ..., |
общие для |
|
|
|||||||
2,000 |
0,0625 |
0,10011 |
0,11807 |
численных решений у2(х) и у3(х), и так далее.
5. Графическое представление численного решения, полученное с по грешностью, не превышающей заданное значение, например, 6„ й 10~*
6.Оценку времени, затраченного на получение численного решения, и ха рактеристики ЭВМ, используемой для расчетов (объем оперативной памяти, тип процессора и его тактовую частоту). Поскольку современные компьютеры обладают высоким быстродействием, могут возникнуть проблемы с оценкой времени работы используемого алгоритма. В этом случае приходится, как пра вило, замерять время, затраченное на многократное исполнение изучаемого ал горитма, повторяемое, например, 1000, 100 000 или большее число раз.
7.Общие выводы по выполненной работе. При этом каждому пункту зада ния должно соответствовать краткое, но четкое описание полученного резуль тата.
Пристальное внимание следует обратить на оформление результатов вы числительных работ. Массивы чисел, получаемые в результате расчетов, не яв ляются конечным результатом вычислительного эксперимента. Это лишь «сы рье» для кропотливой, вдумчивой работы исследователя, основа для размыш лений и выводов. Массивы данных должны быть обработаны и представлены в виде, удобном для последующего анализа, то есть в виде таблиц, рисунков, диаграмм, графиков.
Каждый рисунок следует снабжать исчерпывающим комментарием, разъ ясняющим смысл приведенных данных. Координатные оси должны быть в обя зательном порядке подписаны и размечены. Если координатные оси отражают значения размерных величин, в подписи к рисунку следует указать используе мую размерность. Иногда целесообразно использовать логарифмические коор динаты для большей наглядности представления результатов (рис. В.2).
V
0,14
0,12
0,10
0,08
0,06
0,04
0,02
0,00
Рис. В.2. Зависимость погрешности у решения алгебраического уравнения от номера итерации к в обычных (а) и логарифмических (б) координатах
При использовании ссылок на печатные работы (тезисы докладов, статьи, монографии) следует руководствоваться общепринятой системой оформления списка используемых литературных источников. Список помещается в конце отчета, все цитируемые источники нумеруются и сортируются по алфавиту, либо по порядку цитирования, либо по годам издания. Например:
1. Бояршинов, М.Г. Влияние лесного массива на перенос и рассеяние авто транспортных выбросов / М.Г. Бояршинов // Новое в экологии и безопасности жизнедеятельности: докл. международного экологического конгресса / Балт. гос. техн. ун-т. - СПб, 2000. - С. 235-238.
2.Бояршинов, М.Г. Оценка последствий переноса газового облака над лес ным массивом / М.Г. Бояршинов // Известия РАН. Механика жидкости и газа. - 2 0 0 0 .-№ 4 .-С . 79-87.
3.Бояршинов, М.Г. Модели переноса и рассеяния примесей в раститель ных массивах / М.Г. Бояршинов; Перм. гос. техн. ун-т. - Пермь, 2000. - 143 с.
4.Калиткин, Н.Н. Численные методы / Н.Н. Калиткин. - М.: Наука. Глав ная редакция физико-математической литературы, 1978. - 512 с.
Втексте отчета для ссылок на цитируемые литературные источники ис пользуются квадратные скобки, в которых номера литературных источников из библиографического списка перечисляются через запятую.
Выражаю свою искреннюю признательность заведующему кафедрой «Вы числительная математика и механика» Труфанову Николаю Александровичу и профессору кафедры «Математическое моделирование систем и процессов» Гитману Михаилу Борисовичу за всестороннюю поддержку при подготовке учебного пособия «Численные методы».
Неоценимую помощь при подготовке настоящего пособия оказали студен ты специальностей «Математическое моделирование», «Вычислительная мате матика И механика» Дмитрий Киселев (гр. ММ-90), Алексей Козлинских и Алексей Харченко (гр. ММ-92), Андрей Черепанов и Роман Новокшанов (гр. ММ-93), Михаил Басин, Наталья Шабрыкина, Владимир Кочуров (ММ-94), Ирина Унчанская, Михаил Додкин (ММ-95), Инна Гитман (ММ-96), Евгений Баженов, Андрей Петров (ММ-97), Алексей Столбов, Яна Орбиданс, Елена Столбов^ Ольга Кольцова, Алексей Кетов, Петр Меленев, Павел Малинин, Олег Ипанов (ММ-98), Илья Новожилов и Александр Бородин (КМ-02), при нимавши активное участие в реализации алгоритмов и разработке программ для персональных компьютеров, в выполнении вычислительных эксперимен тов.