WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Ухтинский государственный технический ...»

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Ухтинский государственный технический университет

(УГТУ)

О. М. Кудряшова, Р. А. Нейдорф, В. Н. Пушкин

Вычислительная математика

Учебное пособие

2-е издание, дополненное, переработанное

Допущено Учебно-методическим объединением вузов по университетскому

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

высших учебных заведений, обучающихся по направлению 230100 «Информатика и вычислительная техника»

Ухта 2010 УДК 519.6 (075.8) ББК 22.19 я 7 К 88 Кудряшова, О. М.

Вычислительная математика [Текст] : учеб. пособие / О. М. Кудряшова, Р. А. Нейдорф, В. Н. Пушкин. – 2-е изд., дополн., перераб. – Ухта : УГТУ, 2010. – 104 с.

ISBN 978-5-88179-614-3 Учебное пособие предназначено для студентов очной формы обучения специальности 230102 – «Автоматизированные системы обработки информации и управления».

Цель данного пособия – помочь студентам освоить методы: а) приближенного решения уравнений и систем уравнений, в том числе нелинейных;

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

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

Содержание учебного пособия соответствует рабочей учебной программе по вычислительной математике и рекомендуется к использованию в учебном процессе.

Учебное пособие рекомендовано к изданию Редакционно-издательским советом Ухтинского государственного технического университета.

Рецензенты: А. А. Латышев – заместитель начальника отдела Центра исследований нефтегазовых пластовых систем и термодинамического моделирования филиала ООО «ВНИИгаз»-«СеверНИПИгаз», доцент, к.т.н.;

М. А. Краплин – профессор кафедры «Математика» Донского государственного технического университета, д.т.н.

© Ухтинский государственный технический университет, 2010 © Кудряшова О. М., Нейдорф Р. А., Пушкин В. Н., 2010 ISBN 978-5-88179-614-3 Оглавление Введение

Глава 1. Математические модели, алгоритмы вычислений и способы их оценки

1.1. Математические модели как объекты численных расчётов

1.2. Сущность, задачи и свойства алгоритмов

1.3. Об устойчивости и сложности алгоритмов вычислений

1.4. Оценка сложности вычислений

1.5. Проблема погрешностей вычислений

1.6. Абсолютная и относительная погрешности

1.7. Выводы по главе 1

1.8. Контрольные вопросы

Глава 2. Численное решение уравнений

2.1. Сущность и постановка задачи решения скалярных уравнений

2.2. Методы приближенного решения нелинейных скалярных уравнений

2.2.1. Метод половинного деления

2.2.2. Метод хорд

2.2.3. Метод касательных

2.2.4. Комбинированный метод хорд и касательных

2.2.5. Метод простых итераций

2.3. Сущность и постановка задачи решения векторных уравнений

2.4. Методы приближенного решения векторных уравнений

2.4.1. Метод простых итераций

2.4.2. Метод Зейделя

2.4.3. Метод Ньютона

2.5. Выводы по главе 2

2.6. Контрольные вопросы

Глава 3. Аппроксимация и интерполяция функций

3.1. Сущность и постановка задачи аппроксимации

3.2. Линейная и квадратичная интерполяции

3.3. Метод наименьших квадратов (МНК)

3.4. Сплайн-интерполяция

3.5. Многочлены Лагранжа и Ньютона

3.5.1. Многочлен Лагранжа

3.5.2. Многочлен Ньютона

3.6. Выводы по главе 3

3.7. Контрольные вопросы

Глава 4. Численное дифференцирование и интегрирование.

................. 36

4.1. Аппроксимация производных

4.2. Погрешность численного дифференцирования

4.3. Приближенное вычисление интегралов

4.3.1. Метод прямоугольников

4.3.2. Метод трапеций

4.3.3. Метод Симпсона

4.4. Выводы по главе 4

4.5. Контрольные вопросы

Глава 5. Методы численной оптимизации

5.1. Общие положения теории оптимизации

5.2. Методы многомерной оптимизации.

5.2.1. Метод покоординатного спуска

5.2.2. Метод наискорейшего градиентного спуска

5.2.3. Метод Нелдера-Мида (симплекс-метод)

5.3. Выводы по главе 5

5.4. Контрольные вопросы

Глава 6. Численные методы решения дифференциальных уравнений

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

6.2. Численное интегрирование обыкновенных дифференциальных уравнений.................. 53 6.2.1. Методы Эйлера и Адамса

6.2.2. Методы Рунге-Кутта

6.3. Численное решение уравнений в частных производных

6.3.1. Метод сеток для решения задач математической физики

6.3.2. Метод прогонки

6.4. Выводы по главе 6

6.5. Контрольные вопросы

Глава 7. Контрольные задания и указания к выполнению лабораторной работы

Задание 1. Определение погрешности значений функций

Задание 2. Приближенное решение уравнений

Задание 3. Приближенное решение систем уравнений

Задание 4. Аппроксимация функций

Задание 5. Приближенное вычисление интегралов

Задание 6. Численное интегрирование дифференциальных уравнений

Задание 7. Нахождение минимума функции

Задание 8. Определение профиля температуры в стержне через определенный промежуток времени t1

Глава 8. Пример выполнения лабораторной работы

Задание 1. Определение погрешности значений функций

Задание 2. Приближенное решение уравнений

Задание 3. Приближенное решение систем уравнений

Задание 4. Аппроксимация функций

Задание 5. Приближенное вычисление интегралов

Задание 6. Численное интегрирование дифференциальных уравнений

Задание 7. Нахождение минимума функции

Задание 8. Определение профиля температуры в стержне через определенный промежуток времени t1.

и определение времени выхода на стационарный режим

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Введение

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

Вследствие этого математика прошлого была численной математикой, т. е. ее целью было получение решения в виде числа. Поэтому численное решение прикладных задач всегда интересовало математиков. Крупнейшие представители прошлого сочетали в своих исследованиях изучение явлений природы, получение их математического описания, т. е. математической модели, анализ и поиск решения последней. Появление усложненных моделей потребовало создания специальных (преимущественно численных) методов их решения. Названия некоторых методов свидетельствуют о том, что их разработкой занимались крупнейшие ученые своего времени: Ньютон, Эйлер, Лобачевский, Гаусс, Чебышев, Эрмит и т. д.

Имеет смысл выделить, по меньшей мере, два обстоятельства, которые первоначально обусловили стремление к математизации наук:

во-первых, только применение математических методов позволяет придать количественный характер исследованию того или иного явления материального мира и, как следствие, оценивать и сравнивать результаты;

во-вторых, (и это главное) только математический способ мышления делает возможным эффективное исследование объекта©.

Во второй половине прошлого столетия появился еще один фактор, оказавший сильное воздействие на процессы математизации знаний, быстрое развитие средств вычислительной техники. Применение ЭВМ для решения научных, инженерных и вообще прикладных задач целиком базируется на их математизации. Для настоящего времени характерно резкое расширение приложений математики. Это во многом связано с созданием и развитием средств вычислительной техники. В результате появления ЭВМ менее чем за 40 лет скорость выполнения операций возросла от 0,1 операции в секунду (при ручном счете) до 1 триллиона операций в секунду (на современных ЭВМ).

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

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

© Такой метод исследования называют вычислительным экспериментом, и только такое исследование может считаться в полной мере объективным.

Глава 1. Математические модели, алгоритмы вычислений и способы их оценки

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

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

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

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

Математические модели можно классифицировать по разным признакам.

Основной из них – деление их на статические и динамические.

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

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

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

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

Графически заданные зависимости демонстрируют связь между переменными в непрерывной форме. Они более наглядны для восприятия, но точность отображения связи в них ограничена. Поэтому их используют, в настоящее время, лишь в иллюстративных целях. Простые зависимости отображаются двумерными графиками на плоскости. При большей размерности используются аксонометрические 3D-изображения и семейства двумерных графиков («срезы»).

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

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

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

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

Математические модели делятся также по другим признакам: сосредоточенные и распределенные; детерминированные и вероятностные и т.д. Эти признаки влияют на конкретный вид или структуру модели, а также на способы их решения.

1.2. Сущность, задачи и свойства алгоритмов

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

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

Определение алгоритма. Единого «истинного» определения понятия «алгоритм» нет. Вот перечень наиболее значимых (по степени известности предложивших их авторов) определений:

• «Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность» (Д. Э. Кнут).

• «Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи» (А. Колмогоров).

• «Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату» (А. Марков).

• «Алгоритм — точное предписание о выполнении в определенном порядке некоторой системы операций, ведущих к решению всех задач данного типа» (Философский словарь / Под ред. М. М. Розенталя).

Формальные признаки алгоритмов.

Различные определения алгоритма в явной или неявной форме содержат ряд общих требований к его существу:

• детерминированность или определённость на каждом шаге выполнения следующий шаг работы однозначно определяется состоянием системы;

• понятность алгоритм должен включать только те команды для исполнителя, которые ему доступны, которые входят в его систему команд;

• завершаемость или конечность при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов;

• универсальность алгоритм должен быть применим к разным наборам исходных данных;

• результативность работа алгоритма должна завершаться определенными результатами.

Этот набор формальных признаков действующего алгоритма можно дополнить признаками его корректности:

• алгоритм содержит ошибки, если приводит к получению неправильных результатов, либо не дает результатов вовсе;

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

Профессор Дейкстра первым показал в своих статьях и книге «Дисциплина программирования», как составляются алгоритмы и программы без ошибок с доказательствами их правильности.

1.3. Об устойчивости и сложности алгоритмов вычислений

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

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

1.4. Оценка сложности вычислений

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

Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размерности входа и выхода?».

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

Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа и выхода.

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

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

Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).

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

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

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

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

Два важных представителя:

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

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

Проблема равенства классов P и NP. Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. Математический институт Клэя включил эту проблему в список проблем тысячелетия, предложив награду размером в один миллион долларов США за её решение.

1.5. Проблема погрешностей вычислений

Любые вычисления осуществляются над числами. Но в расчётах числа редко задаются точно. Чаще всего мы знаем их приближенно. Например, даже если точно знать, что участвующее в расчётах число равно 11/5, то записать его, чтобы использовать в расчётах на ЭВМ, в виде десятичной дроби можно только приближенно. При вычислениях на компьютере с такими числами производится огромное число операций, и в результатах возникают ошибки, которые постепенно накапливаются и искажают конечный результат. Таким образом, решение задач на ЭВМ практически всегда является приближенным, т.е.

решение находится с некоторой погрешностью.

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

Количественной характеристикой точности как вводимых в процесс вычисления, так и выводимых в качестве результата чисел является «погрешность». Соответственно месту в процедуре вычисления различают погрешность «исходную» и «результирующую».

Различают следующие основные источники погрешностей:

• погрешности задачи (модели), связанные с самой математической постановкой решаемой содержательной задачи и обусловленные тем, что принятая математическая модель лишь приближенно описывает отражаемое явление;

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

• погрешности метода, которые возникают с приближённым характером используемого численного метода©;

• погрешности округления, которые связаны с самой системой счисления и обусловлены ограниченной разрядной сеткой ЭВМ.

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

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

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

–  –  –

Погрешность функции.

Предположим, что искомая величина у является функцией от параметров а1, а2, …, ап. Известна область n-мерного пространства G, которой принадлежат параметры. Пусть у* – приближенное значение величины у.

Определение: Предельной абсолютной погрешностью значения функции у(a) называется величина:

–  –  –

Величины a в (1.1) – размеры этого прямоугольника, обусловленные i неточностью значений параметров.

Частные случаи:

1) Предельная абсолютная погрешность суммы или разности равна сумме предельных абсолютных погрешностей аргументов:

–  –  –

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

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

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

В качестве дополнительного критерия качества алгоритма выступает понятие его сложности, которая измеряется временем исполнения и объёмом необходимой памяти на носителе данных. Здесь следует отметить представление о диапазоне, которому принадлежит значение сложности: от сложности в лучшем случае до сложности в худшем случае.

Решение задач на ЭВМ практически всегда является приближенным. Определение точности результата является важнейшей математической задачей.

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

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

1.8. Контрольные вопросы

1. Что представляет собой математическая модель?

2. Что может включать в себя математическая модель?

3. Виды математических моделей.

4. Чем характеризуются статические модели?

5. Чем характеризуются динамические модели?

6. Что входит в понятие вычислительного алгоритма?

7. Свойства алгоритма.

8. Раскройте понятие устойчивости алгоритма вычислений.

9. В чем состоит различие временной сложности алгоритма в худшем случае и временной сложности алгоритма в лучшем случае?

10. В чем заключается понятие асимптотической сложности алгоритмов?

11. Что подразумевается под сложностью алгоритма?

12. Какие классы сложности алгоритмов существуют?

13. Что представляют собой погрешности измерений и вычислений?

14. Что служит источниками погрешностей?

15. Какие погрешности являются неустранимыми?

16. Возможности снижения погрешностей.

17. Что представляет собой абсолютная погрешность измерения?

18. Что представляет собой абсолютная погрешность функции?

19. Что представляет собой линейная оценка абсолютной погрешности?

20. Что представляет собой относительная погрешность?

21. Чему равна предельная абсолютная погрешность суммы или разности?

22. Чему равна предельная относительная погрешность произведения или частного?

Глава 2. Численное решение уравнений

2.1. Сущность и постановка задачи решения скалярных уравнений

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

–  –  –

Примером здесь может служить модель процесса изменения теплового состояния химического реактора идеального смешения:

dT = f1 (T ) f 2 (T ), dt где T температура, f1 (T ), f 2 (T ) функции тепловыделения и теплоотвода, соответственно.

Очевидно, что частными решениями дифференциального уравнения (2.1) являются постоянные x = a, при которых f ( x ) = 0. Эти решения принято называть стационарными состояниями или положениями равновесия. В этих состояниях процесс (система) может находиться сколь угодно долго. Но если каким-либо образом процесс вывести из такого состояния, то в течение определенного промежутка времени вслед за этим изменения в системе будут весьма заметны. При этом процесс может эволюционировать либо в сторону исходного стационарного состояния, либо стремиться к другому положению равновесия.

Насколько желательно то или иное стационарное состояние, определяется потребностями практической деятельности. Таким образом, задача отыскания решений уравнения f ( x ) = 0 с физической точки зрения может означать поиск стационарных состояний исследуемого процесса.

Итак, пусть требуется найти корни уравнения:

f ( x) = 0, (2.2)

где f (x) некоторая непрерывная, в общем случае нелинейная функция.

Как правило, на первом этапе с помощью методов дифференциального исчисления производят процедуру отделения (локализации) корней, то есть указывают интервалы, на каждом из которых заведомо располагается ровно один корень уравнения (2.2).

Далее, при обсуждении приближенных методов поиска решений предполагается, что процедура локализации корней произведена, и на рассматриваемом отрезке (a, b) находится только один корень данного уравнения (2.2).

2.2. Методы приближенного решения нелинейных скалярных уравнений

–  –  –

В качестве начального приближения принимаем середину отрезка a+b x0 =. Рассматриваем значения функций f ( a ), f ( x 0 ), f (b). Искомый корень принадлежит тому из отрезков [a, x0] и [x0, b], на концах которого f (x) принимает значения разных знаков. Середина именно этого отрезка будет следующим приближением корня и т.д.

После каждой итерации длина отрезка [x n 1 ; x n ], которому принадлежит корень, уменьшается вдвое.

Итерационный процесс продолжается до тех пор, пока не будет выполнено условие:

–  –  –

В этом методе в качестве приближенных значений корня принимаются первые координаты х0, х1, х2, … точек пересечения хорд, соединяющих два конца участка кривой у = f (x), пересекающего ось 0х (рис. 1).

–  –  –

где – требуемая точность.

Замечание. Для дважды дифференцируемой на (a,b) функции условие (2.5) следует применять в том случае, если на данном отрезке выполняется неравенство f ( x ) f ( x ) 0.

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

–  –  –

Схематично последовательное нахождение приближений к корню рассматриваемым методом изображено на рис. 2. При этом предполагается, что функция у = f (x) дифференцируема на рассматриваемом отрезке.

–  –  –

где – требуемая точность.

Замечание. Условие (2.7) для дважды дифференцируемой функции f (x), как и (2.5), применяется в том случае, если на данном отрезке выполняется неравенство f (x ) f (x ) 0.

В случае, если на отрезке выполняется противоположное неравенство f ( x ) f ( x ) 0, условие (2.7) следует заменить следующим:

f(xn) f (xn - ) 0. При этом в качестве начального приближения следует выбрать x0 = b. Блок-схема расчета, соответствующая данному методу, изображена на рис. 13 (с. 82).

–  –  –

Метод хорд и касательных в случае дифференцируемой функции f (x) можно объединить. Это позволяет приближаться к корню с разных сторон.

Соответствующая схема имеет вид:

–  –  –

где – требуемая точность.

Замечание. В формулах (2.8) верхний индекс,,k” соответствует приближению к корню, полученному по методу касательных, а,,x” – по методу хорд. В случае дважды дифференцируемой функции указанные в (2.8) начальные приближения выбираются в том случае, если на данном отрезке выполняется неравенство f ( x ) f ( x ) 0.

Если же на отрезке выполняется противоположное неравенство f ( x ) f ( x ) 0, то начальными приближениями будут служить:

x ( k ) = b, x ( x ) = a.

–  –  –

При этом начальное приближение х0 должно выбираться из дополнительных соображений.

Достаточным условием сходимости вычислений по схеме (2.8') является выполнение неравенства (х) 1 во всей области, где находится корень и откуда берется начальное приближение.

Замечание 1. Существует сколько угодно способов представления уравнения (2.2) в виде х = (х). Само собой разумеется, что не во всех случаях будет выполняться указанное выше условие сходимости.

Замечание 2.

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

–  –  –

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

В случае участия в реакции молекул двух веществ, такую модель можно представить в виде:

–  –  –

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

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

Система n-алгебраических уравнений относительно n-неизвестных в общем случае может быть записана в виде:

–  –  –

Если левые части уравнений (2.9) имеют вид fi = ai1 x1 +... + ain xn bi, то система (2.9) называется линейной.

Для линейных систем разработано большое количество точных методов (метод Гаусса, правило Крамера, метод отражений и др.), которые характеризуются тем, что при отсутствии вычислительных погрешностей дают точные решения.

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

Для линейных систем большого порядка, а также для нелинейных систем, целесообразно применять итерационные методы. Их разнообразие значительно.

Рассмотрим некоторые из них.

2.4. Методы приближенного решения векторных уравнений

–  –  –

Следует заметить, что существует сколько угодно способов представления (2.9) в виде (2.10).

После этого выбираем из некоторых (зачастую специфических) соображений начальное приближение:

–  –  –

Для сходимости итерационного процесса (2.12) достаточно, чтобы все собственные числа матрицы В были по модулю меньше 1.

Замечание 3. Собственные числа квадратной матрицы B представляют собой корни уравнения det (B E ) = 0, где E – единичная матрица. В общем случае они являются комплексными числами = + i, модуль которых по определению равен = +.

Соответствующая данному методу блок-схема для системы линейных уравнений изображена на рис. 15 (с. 84).

–  –  –

Согласно (2.13) на (k+1)-ом шаге сначала из первого уравнения определяется неизвестная x1 k +1), затем с ее помощью из второго определяется неизвест

–  –  –

Как и в случае метода простых итераций, условиями окончания расчетов по формулам (2.13) могут служить условия малости норм и невязок.

Замечание 1. Необходимым и достаточным для сходимости метода Зейделя является следующее условие: все корни уравнения

–  –  –

Предположим, что требуется найти решение системы (2.9). При этом предполагается, что функции f1 ( x1,…, xn ),…, f n ( x1,…, xn ) дифференцируемы по каждому из своих аргументов.

–  –  –

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

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

2.6. Контрольные вопросы

1. В чем заключается алгоритм приближенного решения уравнений методом половинного деления?

2. Что лежит в основе приближенного решения уравнений методом хорд?

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

4. Что представляет собой комбинированный метод хорд и касательных?

5. Что представляет собой метод простых итераций приближенного решения уравнений?

6. Что служит условием окончания расчетов методом половинного деления?

7. Что служит условием окончания расчетов при решении уравнений методом хорд?

8. Что может служить условием окончания расчетов при решении уравнений методом касательных?

9. Что может служить условием окончания расчетов при решении уравнений методом простых итераций?

10. Приведите условие, которое является достаточным для сходимости метода простых итераций.

11. Перечислите точные методы решений систем линейных уравнений.

12. Что лежит в основе метода Гаусса решения систем линейных уравнений?

13. Что представляет собой норма разности двух последовательных приближений?

14. Что представляют собой невязки уравнений системы?

15. Что может служить условием окончания расчетов при реализации на ЭВМ метода простых итераций?

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

17. В чем заключается метод Зейделя приближенного решения систем уравнений?

18. В чем состоит метод Ньютона приближенного решения систем уравнений?

19. Что собой представляет матрица Якоби системы функций?

20. Какие условия могут служить условиями окончания расчетов при решении систем уравнений каким-либо итерационным методом?

Глава 3. Аппроксимация и интерполяция функций

3.1. Сущность и постановка задачи аппроксимации Предположим, что имеется набор значений аргумента x некоторой функции y = y(x) и соответствующий им набор значений этой функции. Например, это могут быть результаты какого-либо эксперимента, когда на вход исследуемой системы подаются сигналы xi, а на выходе фиксируются сигналы yi, представляющие реакцию системы. Точная зависимость между величинами y и x, как правило, неизвестна. Однако требуется на основе имеющегося конечного набора пар значений (xi; yi) (I = 1,…n) иметь возможность для приближенного вычисления значений данной функции для любых других значений аргумента x из некоторой области.

Задача о представлении зависимости между x и y с помощью некоторой функции (х) так, чтобы отклонение между реальной зависимостью, представленной парами (xi;yi), и зависимостью, определяемой функцией (х), было бы в некотором смысле наименьшим, называется задачей аппроксимации. Сама функция (х) называется аппроксимирующей.

Частный вид аппроксимации, когда функция (х) представляет собой многочлен, принимающий в заданных точках xi значения yi ((xi) = yi, I = 1,…n), называется интерполяцией. При этом точки xi называются узлами интерполяции, а (х) – интерполяционным многочленом.

Если используется один многочлен для рассматриваемой области и для всех узлов, то интерполяция называется глобальной.

Если интерполяционные многочлены строятся отдельно для разных частей рассматриваемой области изменения аргумента x, то интерполяция называется локальной.

Аналогичный смысл имеют понятия локальная и глобальная аппроксимации. Перейдем к рассмотрению конкретных примеров интерполяции.

3.2. Линейная и квадратичная интерполяции

Линейная интерполяция – простейший вид локальной интерполяции. С геометрической точки зрения она состоит в том, что заданные узловые точки соединяются прямолинейными отрезками и график функции f(x) аппроксимируется ломаной, соединяющей точки (xi, f (xi)).

На каждом из интервалов (xi-1, xi) в качестве интерполяционного многочлена используется линейная функция, соответствующая уравнению прямой, проходящей через точки (xi-1; yi-1) и (xi; yi):

–  –  –

Квадратичная интерполяция – другой вид локальной интерполяции.

В качестве интерполяционной функции берется квадратный трехчлен, соответствующий параболе, проходящей через три соседние узловые точки (xi-1,yi-1), (xi, yi), (xi+1, yi+1):

y = aix2 + bix + ci, xi-1 x xi+1.

Уравнения для определения ai, bi, ci:

–  –  –

Приближенное значение функции для любой точки x [x0, xn] находится с помощью интерполяции по трем ближайшим к ней узлам xi-1, xi, xi+1.

Блок-схема приближенного вычисления значений функции, соответствующая данному методу, представлена на рис. 19 (с. 88).

–  –  –

Составим функцию двух переменных a, b, представляющую собой сумму квадратов отклонений значений линейной функции f(x) = ax+b в узловых точках от наблюдаемых значений yk :

–  –  –

Решение линейной системы (3.3) единственно, и именно оно определяет наилучшую в среднеквадратичном смысле приближенную зависимость y ax + b.

По схожему принципу в рамках МНК можно получить систему уравнений для определения параметров приближенной параболической зависимости

y ax + bx + c :

–  –  –

Широкое распространение нашла интерполяция кубическими сплайнами – многочленами третьей степени.

В этом случае на каждом отрезке, включающем три соседних узла, функция аппроксимируется многочленом:

S(x) = ai + bi(x-xi-1) + ci(x-xi-1)2 + di(x-xi-1)3, xi-1 x xi+1.

Часть из 4n-условий, необходимых для определения коэффициентов ai, bi,

ci, di, вытекают из условий прохождения графика функции y = S(x) через заданные точки:

–  –  –

где hi = xi – xi-1, i =1, 2, …, n.

Другие условия вытекают из требований непрерывности первых и вторых производных функций S(x) в узлах интерполяции:

–  –  –

где i = 1, 2, …, n–1.

Еще два соотношения получаются из условий закрепления концов сплайна.

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

–  –  –

Далее, используя (3.13) и найденные по формулам (3.14) прогоночные коэффициенты, вычисляем все неизвестные ci. Вслед за этим по формулам (3.9), (3.10) определяем bi, di. Тем самым будет построен сплайн-полином S(x).

Замечание: если |Bi| |Ai| + |Di| для i и хотя бы для одного i выполняется строгое неравенство, то система (3.12) имеет единственное решение.

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

–  –  –

Рассмотрим случай равноотстоящих узлов xi – xi-1 = h = const, i = 1, 2, …, n.

Величина h называется шагом.

Определение.

Разности значений функции y0 = y1 – y0 = f (x0 + h) – f (x0), y1 = y2 – y1 = f (x0 + 2h) – f (x0+h), …, yn-1 = yn – yn-1 = f (x0 + nh) – f (xo + (n – 1)h) называются первыми конечными разностями;

• разности 2y0 = y1 – y0, 2y1 = y2 – y1, … называются вторыми конечными разностями;

• разности kyi = k – 1yi+1 – k – 1yi называются конечными разностями k-го порядка.

–  –  –

Полученное выражение аппроксимирует функцию y = f (x) на всем отрезке [x0, xn]. Однако для повышения точности и уменьшения числа слагаемых в (3.18) ограничимся случаем t1, (т.е. для x [x0, x1] ).

Для x [x1, x2] вместо x0 лучше взять x1.

В результате получим:

–  –  –

3.6. Выводы по главе 3 Под аппроксимацией понимают приближенное представление зависимости между двумя переменными x и y в виде некоторых, выбираемых из определенного класса функций на основе имеющегося конечного набора пар соответствующих друг другу значений этих переменных (xi; yi) (i=1,…n). При этом искомая зависимость должна быть оптимальной в смысле близости к наблюдаемым значениям.

Аппроксимация с помощью многочленов носит название интерполяции.

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

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

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

3.7. Контрольные вопросы

1. Что понимают под аппроксимацией функций?

2. Что понимают под интерполяцией функций?

3. Раскройте понятия локальной и глобальной интерполяции?

4. Какие существуют виды интерполяции?

5. Что представляет собой линейная интерполяция?

6. Что представляет собой квадратичная интерполяция?

7. Что представляет собой сплайн-интерполяция?

8. В чем заключается метод наименьших квадратов?

9. Что представляет собой многочлен Лагранжа?

10. Что представляет собой многочлен Ньютона?

11. В чем сходство и различие между многочленами Лагранжа и Ньютона?

Глава 4. Численное дифференцирование и интегрирование

–  –  –

Соответствующие значения функции будем обозначать yi = f (xi).

В зависимости от способа вычисления конечных разностей аппроксимация (4.1) производной в одной и той же точке может быть различной:

• если y1 = y1 – y0, то для производной функции в точке x1 выражение

–  –  –

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

b f ( x)dx = F (b) F (a ), а где F(x) – первообразная функции f (x), бессмысленно.

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

Рассмотрим некоторые из наиболее распространенных методов приближенного вычисления интегралов. Далее всюду предполагается, что подынтегральная функция f (x) непрерывна на [a, b].

4.3.1. Метод прямоугольников

–  –  –

Ее геометрический смысл также очевиден (рис. 3).

Разумеется, существуют и другие формулы прямоугольников (например средних), которые отличаются друг от друга выбором точек из элементарных отрезков [xi, xi+1]. В формуле (4.4) это левые концы элементарных отрезков, а в формуле (4.5) – правые.

В практических расчетах при заданной точности можно применять одновременно формулы (4.4) и (4.5). Если обозначить значения правых частей в этих формулах соответственно I и I, то условием достижения требуемой n n точности в случае монотонной на [a,b] функции f (x) может служить неравенство: I I. Блок-схема, описывающая данный метод, изображена на рис. 22 n n (с. 91).

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

–  –  –

Геометрически применение формулы (4.6) означает замену графика подынтегральной функции y = f (x) ломаной, звенья которой последовательно соединяют точки ( xi ; f i ), i = 0, 1,..., n.

Для достижения требуемой точности можно использовать следующий алгоритм. Вычисляем приближенное значение интеграла по формуле (4.6) для начального числа элементарных отрезков n0. Получим значение I 0. Удвоим число элементарных отрезков n1 =2 n0 и снова применим формулу (4.6). Получим значение I1, после чего опять удвоим число отрезков и т.д. В результате получим последовательность приближенных значений интеграла I0, I1, …,Ik, …

Расчеты следует прекратить тогда, когда будет выполняться неравенство:

–  –  –

Известно, что погрешность формулы Симпсона порядка четвертой степени шага разбиения h (главный член погрешности, взятый по абсолютной велиh 4 f (4) ( x), где f (4) ( x) – четвертая производная подынтегральной чине, равен функции; x – некоторое значение аргумента из области интегрирования).

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

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

4.5. Контрольные вопросы

1. Что лежит в основе аппроксимации производных функций?

2. Что представляет собой и какова погрешность аппроксимации производных с помощью левых разностей?

3. Что представляет собой и какова погрешность аппроксимации производных с помощью правых разностей?

4. Что представляет собой и какова погрешность аппроксимации производных с помощью центральных разностей?

5. Что лежит в основе приближенного вычисления определенных интегралов?

6. В чем суть метода прямоугольников приближенного вычисления определенных интегралов?

7. Как добиться требуемой точности при вычислении интеграла от монотонной функции методом прямоугольников?

8. В чем суть метода трапеций приближенного вычисления определенных интегралов?

9. На чем основан метод Симпсона приближенного вычисления определенных интегралов?

–  –  –

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

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

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

u = u ( x, x,..., x ).

1 2 n Аргументы функции u(x) – xi, i[1, n], называются параметрами или факторами.

Процесс оптимизации заключается в поиске таких значений xi, i[1, n], при которых целевая функция u = u(x1, x2, …, xn) будет иметь экстремум.

Если целевая функция зависит только от одного параметра (n = 1), то поиск ее экстремума называется одномерной задачей оптимизации, если же n 2, то имеет место многомерная задача оптимизации.

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

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

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

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

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

C ( x, x, …, x ) = 0, 1 1 2 n

–  –  –

Причем число тех и других может быть любым.

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

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

При решении практических задач оптимизации целевая функция зависит от нескольких параметров. При этом, если в некоторой области проектирования требуется отыскать минимум функции u(x1, x2, …, xn), n 2, то интервалы изменения параметров x1, x2, …, xn можно разбить на некоторое количество подынтервалов, в узлах, полученных в результате такой процедуры, сеток вычислить значения целевой функции и выбрать наименьшее из них. Однако проведенные оценки показывают, что подобные методы общего поиска для решения задач многомерной оптимизации не подходят, поскольку требуют очень большого объема вычислительных операций и машинного времени.

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

–  –  –

Пусть в n-мерном пространстве проектирования, определенном, например, в виде xi[ai, bi], i[1, n], задано начальное приближение вектора проектных параметров x :

–  –  –

Значение координаты x1, при котором имеет место минимум целевой функции, обозначим как x11.

На следующем шаге зафиксируем значения координат x11, x30, …, xn0 и отыщем:

–  –  –

который, предположим, будет иметь место при x2 = x21 и так далее.

В результате после n шагов получим:

u(x11, x21, …, xn1) u(x10, x20, …, xn0), и, таким образом, после одной итерации покоординатного спуска осуществляется переход от значения u( x0 ) к значению u( x1 ), где:

–  –  –

На следующей итерации описанная пошаговая процедура покоординатного спуска повторяется и так до тех пор, пока на некоторой k-ой итерации для задаваемой точности не выполнится, например, условие:

u( xk )-u( xk 1 ).

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

–  –  –

Из курса математического анализа известно, что направление наибольшего возрастания функции нескольких переменных характеризуется ее вектором градиента:

–  –  –

где h – шаг спуска, x0 – начальное приближение к точке минимума. Если в выражении (5.1) шаг спуска h = const, то данная итерационная процедура представляет собой метод градиентного спуска. Завершение итерационного процесса (5.1) может быть осуществлено при выполнении, например, условия:

grad u ( xk +1 ) или

–  –  –

где – задаваемая точность.

Недостатком метода градиентного спуска является его сложность реализации, поскольку на каждом k-ом шаге оптимизации необходимо вычислять частные производные целевой функции, что особенно затруднительно, если u( xk ) представлена не в аналитическом виде.

Более свободен от указанного недостатка метод наискорейшего градиентного спуска, отличающийся тем, что в выражении (5.1) величина h const, а движение из точки u( xk ) в точку u( xk +1 ), k = 0, 1, 2, …, осуществляется до тех пор, пока целевая функция убывает, достигая минимума вдоль этого направления, и только потом вновь вычисляется вектор градиента, чтобы изменить направление движения.

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

Величина шага h на некоторой k-ой итерации может последовательно изменяться до тех пор, пока не будет найдено минимальное значение u( x ) вдоль данного направления, что требует неоднократного вычисления u( x ), либо параметр h может быть выбран из условия:

u ( xk +1 ) = min u ( xk h grad u ( xk )), k = 0, 1, 2, …, h что сводится к минимизации данной функции по одной переменной h.

Во втором варианте выбора h отпадает необходимость неоднократного вычисления целевой функции, однако приходится решать задачу одномерной оптимизации функции u ( xk h grad u ( xk )) по параметру h.

–  –  –

Метод Нелдера-Мида, по сравнению с градиентными методами, оказывается значительно более простым в реализации, является очень надежным, а при n 6 – одним из самых эффективных.

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

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

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

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

Метод Нелдера и Мида стал продолжением метода симплексного поиска Спендли, Хекста и Химсворта, разработанный в связи со статистическим планированием эксперимента. Здесь следует напомнить, что регулярные многогранники в пространстве Еп являются симплексами.

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

–  –  –

Рис. 7 – Последовательность регулярных симплексов На рис. 7 приведена последовательность регулярных симплексов, полученных при минимизации f ( x ). Пунктиром обозначена проекция.

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

В методе Нелдера и Мида минимизируется функция n-независимых переn менных с использованием (n+1) вершин деформируемого многогранника в Е.

Каждая вершина может быть идентифицирована вектором x. Вершина (точка) в Еn, в которой значение f ( x ) максимально, проектируется через центр тяжести (центроид) оставшихся вершин. Улучшенные (более низкие) значения целевой функции находятся последовательной заменой точки с максимальным значением f ( x ) на более «хорошие» точки, пока не будет найден минимум f ( x ).

–  –  –

( ) (k ) где – произвольное малое число; f xn+ 2 – значение целевой функции (k ) в центре тяжести xn+2.

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

Коэффициент вводится для растяжения вектора поиска в случае, если отражение дает вершину со значением f ( x ), меньшим, чем наименьшее значение f ( x ), полученное до отражения.

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

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

В качестве удовлетворительных значений этих параметров при оптимизации без ограничений Нелдер и Мид рекомендовали:

= 1, = 0,5 и = 2.

На рис. 27 (с. 96) приведена блок-схема поиска оптимума функции нескольких переменных методом деформируемого многогранника.

5.3. Выводы по главе 5 К задаче об отыскании экстремума унимодальной функции нескольких переменных сводится решение многих прикладных проблем. Выбор метода отыскания оптимума определяется как видом самой функции (непрерывно дифференцируемая или заданная таблично, линейная либо нет и др.), так и наличием или отсутствием дополнительных условий (ограничений). Задачи отыскания экстремума линейной функции при наличии линейных ограничений в виде уравнений и/или неравенств относятся к курсу линейного программирования и здесь не рассматриваются.

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

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

5.4. Контрольные вопросы

1. Что подразумевается под процессом оптимизации?

2. Что представляет собой одномерная задача оптимизации?

3. Что в общем виде представляет собой многомерная задача безусловной оптимизации?

4. Какие существуют типы ограничений в задачах на условный оптимум?

5. Приведите известные вам методы одномерной оптимизации.

6. Перечислите известные вам методы многомерной оптимизации.

7. В чем состоит метод покоординатного спуска?

8. Какое направление характеризует градиент функции?

9. В чем состоит метод наискорейшего градиентного спуска?

10. В чем состоит метод Нелдера-Мида?

11. Перечислите операции, используемые в методе Нелдера-Мида.

Глава 6. Численные методы решения дифференциальных уравнений

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

–  –  –

Заменив в уравнении (6.1) производную на конечную разность, получим расчетную формулу Эйлера для приближенного вычисления значения функции

yi+1 = y ( xi + hi ) при условии, что известно значение yi = y ( xi ) :

–  –  –

где hi = xi +1 xi, i = 0,1, ….

При помощи (6.2) осуществляется дискретная цепь шагов hi, при этом на каждом шаге определяется приближенное значение yi+1, соответствующее значению аргумента xi+1 = xi + hi. В классическом случае величина шага

hi = h = const. Разумеется, чем меньше шаг h по переменной x, тем ближе расположена ломаная, последовательно соединяющая точки ( xi, y i ), к интегральной кривой искомого решения задачи Коши. Погрешность формулы (6.2) порядка О(h2). Более точной, чем (6.2), является расчетная формула:

–  –  –

позволяют явно определить yi+1.

По аналогии с (6.3), формулы (6.4) можно называть явными формулами Адамса.

Блок-схема, соответствующая данному методу, представлена на рис. 24 (с. 93).

–  –  –

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

Условия, подобные (6.9), носят название граничных условий I рода.

Условия на границе могут иметь и другую форму.

Например, на одной из границ может быть задан градиент температуры:

T (t,0) = (t ). (6.10) x Соотношения типа (6.10) принято называть граничными условиями II рода.

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

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

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

Для численного решения уравнений математической физики большое применение нашел метод сеток, описываемый далее на примере задач (6.7) - (6.9).

Описание метода сеток

Основу метода сеток приближенного решения задачи составляют следующие принципы:

1) производные функций заменяются отношениями приращений функций и приращений независимых переменных:

–  –  –

Целесообразность выбора равномерной или неравномерной сетки диктуется условиями конкретной задачи.

Дискретная область состоит из точек с координатами (xi, tj).

Для простоты далее будем рассматривать равномерные сетки.

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

Например, в задаче (6.7) - (6.9) можно ввести следующие безразмерные величины (а2 полагается постоянным):

–  –  –

Вернемся к разностной схеме (6.16).

Предположим, что она является явной. Тогда нетрудно заметить, что знаj +1 чения Ti при известных значениях Ti на j-ом слое вычисляются непосредственно из (6.16).

Таким образом, процедура счета чрезвычайно проста. По известным из (6.17) значениям Ti на нулевом временном слое находим значения Ti во всех узлах первого временного слоя. Аналогично с их помощью определяем все значения на втором слое (t = t2) и так далее до определенного, наперед указанного m-слоя.

Эта схема, несмотря на простоту, обладает рядом недостатков, главный из которых состоит в том, что при определенных соотношениях между шагами t и x схема становится неустойчивой, то есть в профиле рассчитываемой переменной (в нашем примере ее представляет температура) появляются не обусловленные физическим смыслом участки выпуклости и вогнутости – «рябь».

Причем амплитуда «ряби» от слоя к слою растет. При расчетах на ЭВМ это приводит к переполнению и аварийному останову.

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

Неявная схема, согласно которой дискретные значения переменной в правой части (6.16) берутся на следующем (j+1)-ом слое, лишена этого недостатка.

Она является абсолютно устойчивой, то есть профиль Т не испытывает «возмущений» для любых t и x. При этом следует заметить, что для устойчивости неявной схемы необходимы дополнительные условия, которые в подавляющем большинстве случаев выполняются.

Более подробно о достоинствах и недостатках различных разностных схем в [2, 3, 4]. Все, что будет рассматриваться далее, будет касаться только неявных схем.

При «неявном» подходе мы на каждом (j+1)-ом слое получаем систему плинейных уравнений (6.16) с п-неизвестными Ti j +1, i = 1, 2,..., n. Очевидно, что матрица такой системы является трехдиагональной (везде у нее, кроме главной и двух соседних диагоналей, располагаются нули).

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

–  –  –

Далее, из первого равенства (6.22), следует, что 1 = 1, 1 = 1. После этого вычисляются все i, i. Процедура вычисления коэффициентов i, i по формулам (6.24) носит название прямой прогонки.

После определения i, i находим, принимая во внимание (6.23), искомые значения Ti на (j+1)-ом слое, причем, как нетрудно установить:

2 + 2 n +1 Tn +1 =.

1 2 n +1 Заметим, что при задании на правой границе температуры оно эквивалентно равенству Tn+1 = 2.

Процедура вычисления Ti по формулам (6.23) называется обратной прогонкой. Смысл названия очевиден.

Замечание 1.

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

Ai 0, Bi 0, Ci Ai + Bi, 0 k 1 (k = 1, 2). (6.25) Эти условия обеспечивают разрешимость системы (6.20) и устойчивость метода прогонки.

Очевидно, что для коэффициентов (6.21) условия (6.25) выполняются.

Замечание 2.

Погрешность аппроксимации как явной, так и неявной схем составляет 0(t + x2), где t – шаг вдоль оси t; x – шаг вдоль оси 0x.

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

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

6.5. Контрольные вопросы

1. Что представляет собой задача Коши для обыкновенного дифференциального уравнения 1-го порядка?

2. Что лежит в основе приближенного интегрирования обыкновенных дифференциальных уравнений?

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

4. В чем принципиальная разница между явными и неявными методами интегрирования обыкновенных дифференциальных уравнений?

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

6. В чем заключается явный метод Эйлера интегрирования обыкновенных дифференциальных уравнений?

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

8. Каков порядок погрешности при использовании метода Эйлера?

9. В чем заключается явный метод Адамса интегрирования обыкновенных дифференциальных уравнений?

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

11. Каков порядок аппроксимации при использовании метода Адамса?

12. В чем состоит общий смысл методов Рунге-Кутта?

13. Приведите расчетные формулы метода Рунге-Кутта 3-го порядка интегрирования обыкновенных дифференциальных уравнений.

14. Приведите расчетные формулы метода Рунге-Кутта 4-го порядка интегрирования обыкновенных дифференциальных уравнений.

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

16. Что, кроме уравнения в частных производных, входит в задачу о распространении тепла в некоторой среде?

17. Что представляет собой процедура обезразмеривания задачи?

18. Для решения каких задач может быть использован метод сеток?

19. Чем диктуется выбор между равномерной и неравномерной сетками при решении конкретной задачи?

20. Что отличает явную разностную схему от неявной?

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

22. В чем заключаются вычисления на этапе прямой прогонки?

23. В чем заключаются вычисления на этапе обратной прогонки?

24. Какова погрешность аппроксимации при использовании метода сеток при решении о распространении тепла в тонком стержне?

–  –  –

Задание 1. Определение погрешности значений функций Вычислите значения величин х и у, оцените абсолютные и относительные погрешности этих значений при заданных значениях параметров a, b, c (указанные значащие цифры каждого из них являются верными).

–  –  –

Дано уравнение f (x) = 0. Требуется:

1. Локализовать действительные корни уравнения.

2. Осуществить вручную 3 шага вычислений одного из корней указанным методом.

3. Составить программу, реализующую на компьютере указанный в варианте метод расчета.

4. Найти все корни уравнения с точностью = 10 – 4 с помощью программы.

В вариантах с номерами 5п-4 использовать метод половинного деления;

с номерами 5п-3 – метод хорд; с номерами 5п-2 – метод касательных; с номерами 5п-1 – комбинированный метод хорд и касательных; с номерами 5п – метод простых итераций.

Здесь п – натуральное число (1, 2, 3 и т. д.).

–  –  –

Задание 3. Приближенное решение систем уравнений Дана система четырех линейных уравнений с четырьмя неизвестными х1, х2, х3, х4.

Расширенная матрица этой системы имеет вид:

–  –  –

где В = (b1, b2, b3, b4)T столбец свободных членов системы Ах = В.

Требуется:

1. Найти приближенно решение данной системы, сделав три итерации вручную и взяв в качестве начального приближения нулевой набор ( 0) T x = (0;0;0;0).

2. Составить программу для нахождения приближенного (с заранее заданной точностью ) решения данной системы.

В нечетных вариантах применить метод простых итераций, в четных метод Зейделя.

В программе предусмотреть возможность варьирования точности, вывода как искомых решений, так и невязок:

–  –  –

3 4 2 3 1 1 3 1 1 4 ~ 2 9 ~ 4 9 3) ; 4) ;

А= А= 1 5 12 3 3 1 4 2 3 9 1 1 3 1 1 4 ~ 3 ~ 4 10 5) ; 6) ;

А= А= 1 5 12 5 9 12 ~ 2 ~ 4 9 7) ; 8) ;

А= А= 1 5 1 3 1 2 2 3 2 4 1 6 ~ 2 10 ~ 3 90 9) ; 10) А = ;

А= 2 4 12 4 10 2 3 9 ~ 4 8 ~ 4 11) ; 12) А = ;

А= 2 12 2 1 2 4 2 2 2 1 4 1 5 ~ 3 10 1 ~ 3 9 1

13) А = ; 14) А = ;

1 5 12 4 11 8 ~ 3 10 1 ~ 3 11 1 3

15) А = ; 16) А = ;

1 6 2 4 3 3 2 4 9 1 4 1 3 ~ 2 1 ~ 3 12 1

17) А = ; 18) А = ;

1 14 2 4 11 2 1 3 2 1 1 ~ 2 93 ~ 4 10

19) А = ; 20) А = ;

1 5 12 3 9 1 2 1 3 6 ~ 1 10 3 4 9 1 0 2 2 ~ 3

21) А = ; 22) А = ;

2 1 4 12 2 12 ~ 1 2 ~ 4 10 0

23) А = ; 24) А = ;

3 2 2 11 2 1 2 1 3 2 1 3 ~ 3 9 ~ 3 10

25) А = ; 26) А =.

4 5 1 1 10 9

–  –  –

Даны наборы десяти значений независимой переменной x и соответствующих им значений функции y. Требуется:

1) Методом наименьших квадратов (МНК) найти аппроксимацию зависимости y(x) в виде y = ax + bx + c. С помощью найденной зависимости найти значения y ( x1 ) и y ( x 2 ).

2) Найти те же значения y ( x1 ) и y ( x2 ) методом квадратичной интерполяции (МКИ).

3) Программными средствами построить на одной координатной плоскости параболы, полученные с помощью МНК и с помощью МКИ.

–  –  –

Задание 5. Приближенное вычисление интегралов b

Дан интеграл f ( x ) dx. Требуется:

a

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

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

В вариантах с номерами 3n-2 использовать метод прямоугольников, в вариантах с номерами 3n-1 – метод трапеций, в вариантах с номерами 3n – метод Симпсона (n = 1, 2,…).

–  –  –

Задание 6. Численное интегрирование дифференциальных уравнений Дано обыкновенное дифференциальное уравнение y = f ( x, y ).

Требуется приближенно найти частное решение этого уравнения, удовлетворяющее начальному условию y (0) = y 0.

Для этого следует:

1) Вычислить вручную, с шагом h = 0.1 пять последовательных значений искомого частного решения (в четных вариантах методом Эйлера, в нечетных – методом Адамса).

2) Составить программу для расчета и построения на компьютере соответствующей этому решению интегральной кривой. Ограничиться значениями аргумента на отрезке [0;1]. В вариантах с четными номерами расчеты провести с использованием как метода Эйлера, так и метода Рунге-Кутта 3-го порядка; в вариантах с нечетными номерами – как метода Адамса, так и метода Рунге-Кутта 4-го порядка. В программах предусмотреть возможность варьирования шага h.

–  –  –

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

В программе должна быть предусмотрена возможность варьирования точности. В вариантах с номерами 3n-2 использовать метод покоординатного спуска, в вариантах с номерами 3n-1 – метод наискорейшего градиентного спуска, в вариантах с номерами 3n – метод Нелдера-Мида (n = 1, 2, …).

–  –  –

В приведенных ниже вариантах заданий предполагается решение разностным методом одномерного уравнения теплопроводности (6.7) без источников ( f (x, t) 0).

Заданы значение коэффициента температуропроводности а2 вещества стержня, начальное и граничные условия в виде (6.8) и (6.9) соответственно.

Требуется определить профиль температуры в стержне через определенный промежуток времени t1.

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

1. Уравнение (6.7), начальное и граничные условия приводятся к безразмерному виду (не обязательный, но удобный прием).

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

3. Решаются сеточные уравнения (методом прогонки в случае неявной схемы).

4. Анализируется полученное решение и сравнивается с точным. Последнее может быть получено методом Фурье разделения переменных [1].

В случае неявной схемы можно рекомендовать следующий алгоритм решения сеточных уравнений типа (6.20):

1. Вводится x и, соответственно, размерности массивов Ti, i, i. Вводится t и, соответственно, число временных слоев.

2. В соответствии с начальным условием заполняется массив Ti (первый временной слой, j = 1).

3. Определяются значения 1, 1 в соответствии с левым граничным условием.

4. Осуществляется прямая прогонка, определяются значения элементов массивов i, i; i = 2, 3,..., n+1.

5. Осуществляется обратная прогонка, определяется массив Ti (i = 1,..., n+1) на (j + 1)-ом слое.

6. Если временной слой конечный, то расчет завершен.

7. Если временной слой промежуточный, то производится возврат к п. 3 с целью вычисления Ti на следующем слое.

Начальный профиль температуры и профиль в момент времени t1 требуется представить графически.

Кроме того, в задании необходимо найти время, за которое в стержне установится стационарное (не зависящее от времени) распределение температуры. Блок-схема данного метода представлена на рис. 29 (с. 99).

Формулировка задания

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

На концах стержня в течение всего времени поддерживаются постоянные температуры (Т1 – на левом, Т2 – на правом).

Предполагается, что процесс распределения тепла подчиняется уравнению (6.7).

Требуется:

1) Составить уравнение теплопроводности и соответствующие задаче начальное и граничные условия.

2) Привести задачу к безразмерному виду.

3) Решить полученное уравнение методом сеток, то есть определить дискретное распределение температуры в момент времени t1. Реализацию метода произвести на ЭВМ.

4) Определить в ходе расчета время, за которое в стержне установится стационарное распределение температуры (см. замечание 2).

5) Оценить точность полученного решения.

Замечание 1:

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

Таблица 3 – Физические характеристики веществ

–  –  –

Задание 2. Приближенное решение уравнений

Дано уравнение f (x) = 0. Требуется:

1) локализовать действительные корни уравнения;

2) осуществить вручную 3 шага вычислений одного из корней методом касательных;

3) составить программу, реализующую на компьютере указанный метод расчета;

4) найти все корни уравнения с точностью = 10 – 2 с помощью программы.

Рис.13 Блок-схема, реализующая метод касательных для случая x0 = a

Даны наборы десяти значений независимой переменной x и соответствующих им значений функции y. Требуется:

1. Методом наименьших квадратов (МНК) найти аппроксимацию зависимости y(x) в виде y = ax + bx + c. С помощью найденной зависимости найти значения y ( x1 ) и y ( x 2 ).

2. Найти те же значения y ( x1 ) и y ( x 2 ) методом квадратичной интерполяции (МКИ).

3. Программными средствами построить на одной координатной плоскости параболы, полученные с помощью МНК и с помощью МКИ.

–  –  –

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

–  –  –

Результат работы программы Рис. 21 – Параболы, полученные с помощью МНК и с помощью МКИ, построенные программными средствами на одной координатной плоскости

–  –  –

Рис. 22 – Блок-схема, реализующая метод прямоугольников Задание 6. Численное интегрирование дифференциальных уравнений Дано обыкновенное дифференциальное уравнение y = f ( x, y ).

Требуется приближенно найти частное решение этого уравнения, удовлетворяющее начальному условию y (0) = y 0.

Для этого следует:

1. Вычислить вручную (с шагом h = 0,1) пять последовательных значений искомого частного решения.

2. Составить программу для расчета и построения на компьютере соответствующей этому решению интегральной кривой.

Ограничиться значениями аргумента на отрезке [0;1] методом Эйлера и методом Рунге-Кутта 3-го порядка. В программах предусмотреть возможность варьирования шага h.

Рис. 24 – Блок-схема, реализующая метод Адамса Рис. 25 – Блок-схема, реализующая метод Рунге-Кутта четвертого порядка Результат работы программы Рис. 26 – Реализация методов Адамса и Рунге-Кутта четвертого порядка

–  –  –

1. Составить программу, реализующую метод Нелдера-Мида.

2. Найти минимум функции f ( x ) = ( x1 2) + ( x 2 + 3) + x3 требуемой точности с помощью программы.

–  –  –

Задание 8. Определение профиля температуры в стержне через определенный промежуток времени t1 и определение времени выхода на стационарный режим Написать программу, реализующую метод сеток для алюминиевого стержня длины l = 0,1м, первоначально имеющего постоянную температуру Т0 = 273°К (°К – градусы в шкале Кельвина).

На левом конце его в дальнейшем поддерживается начальная температура Т1 = Т0, а на правом – Т2 = 373°К.

A

–  –  –

Рис. 29 – Блок-схема метода сеток Результат работы программы в начальный момент времени Рис. 30 – Реализация метода сеток в начальный момент времени Результат работы программы в момент безразмерного времени t1 = 0,1 Рис. 31 Реализация метода сеток в момент времени t1 = 0,1 Результат работы программы в момент выхода на стационарный режим (ему соответствует t1 = 0,5) Рис. 32 – Реализация метода сеток в момент выхода на стационарный режим

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Уравнения в частных производных математической физики [Текст] / Н. С. Кошляков [и др.]. М. : Высшая школа, 1970. – 712 с.

2. Самарский, А. А. Введение в теорию разностных схем [Текст] / А. А. Самарский. – М. : Наука, 1971. – 553 с.

3. Самарский, А. А. Методы решения сеточных уравнений [Текст] / А. А. Самарский. – М.: Наука, 1978. – 591 с.

4. Самарский, А. А. Введение в численные методы [Текст] / А. А. Самарский. – М.: Наука, 1982. – 269 с.

5. Химмельблау, Д. М. Прикладное нелинейное программирование [Текст] / Д. М. Химмельблау. – М.: Мир, 1975. – 534 с.

–  –  –

План 2010 г., позиция 12. Подписано в печать 11.11.2010 г.

Компьютерный набор. Гарнитура Times New Roman.

Формат 60x84 1/16. Бумага офсетная. Печать трафаретная.

Усл. печ. л. 6,0. Уч.-изд. л. 5,7. Тираж 150 экз. Заказ № 247.

Ухтинский государственный технический университет.

169300, Республика Коми, г. Ухта, ул. Первомайская, д. 13.

Отдел оперативной полиграфии УГТУ.





















 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.