УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ ОП.10. ЧИСЛЕННЫЕ МЕТОДЫ (ТЕОРЕТИЧЕСКИЙ БЛОК) ПО СПЕЦИАЛЬНОСТИ Программирование в компьютерных системах
ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ, НАУКИ И МОЛОДЕЖНОЙ ПОЛИТИКИ ВОРОНЕЖСКОЙ ОБЛАСТИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКОЙ ОБЛАСТИ
«СЕМИЛУКСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИКО-ЭКОНОМИЧЕСКИЙ КОЛЛЕДЖ»
М.Д. Евдокимова
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС
ПО ДИСЦИПЛИНЕ
ОП.10. ЧИСЛЕННЫЕ МЕТОДЫ
(ТЕОРЕТИЧЕСКИЙ БЛОК)
ПО СПЕЦИАЛЬНОСТИ
230115 Программирование в компьютерных системах
ДЛЯ СТУДЕНТОВ ОЧНОЙ ФОРМЫ ОБУЧЕНИЯ
Семилуки. 2014
Одобрено методическим советом ГОБУ СПО ВО «СГТЭК»
Автор-составитель: Евдокимова М.Д., преподаватель ГОБУ СПО ВО «СГТЭК»
Учебно-методический комплекс по дисциплине Численные методы адресован студентам очной формы обучения.
УМКД включает теоретический блок, перечень практических занятий, задания по самостоятельному изучению тем дисциплины, вопросы для самоконтроля, а также вопросы и задания по промежуточной и итоговой аттестации.
© Евдокимова М.Д., 2014
©ГОБУ СПО ВО «СГТЭ К»
СОДЕРЖАНИЕ
Наименование разделов
стр
Введение
4
Образовательный маршрут
6
Содержание дисциплины
7
Раздел 1. Действия над приближенными числами
9
Раздел 2. Численные методы решения основных математических задач
21
Контроль и оценка результатов освоения учебной дисциплины
79
Информационное обеспечение дисциплины
81
УВАЖАЕМЫЙ СТУДЕНТ!
Учебно-методический комплекс по дисциплине Численные методы создан Вам в помощь для работы на занятиях, при выполнении домашнего задания и подготовки к текущему и итоговому контролю по дисциплине.
УМК по дисциплине включает теоретический блок, содержание практических занятий, задания для самостоятельного изучения тем дисциплины, вопросы для самоконтроля.
Приступая к изучению новой учебной дисциплины, Вы должны внимательно изучить список рекомендованной основной и вспомогательной литературы. Из всего массива рекомендованной литературы следует опираться на литературу, указанную как основную.
По каждой теме в УМК перечислены основные понятия и термины, вопросы, необходимые для изучения (план изучения темы), а также информация по каждому вопросу из подлежащих изучению. Наличие теоретической информации по теме позволит Вам вспомнить ключевые моменты, рассмотренные преподавателем на занятии.
После изучения теоретического блока приведен перечень практических занятий, выполнение которых обязательно. Наличие положительной оценки по практическим необходимо для получения допуска к экзамену по дисциплине, поэтому в случае отсутствия на уроке по уважительной или неуважительной причине Вам потребуется найти время и выполнить пропущенную работу. В процессе изучения дисциплины предусмотрена самостоятельная внеаудиторная работа, включающая решение задач, углубленную проработку тем, составление информационных таблиц.
По итогам изучения дисциплины проводится экзамен.
В результате освоения дисциплины Вы должны уметь:
использовать основные численные методы решения математических задач;
разрабатывать алгоритмы и программы для решения вычислительных задач, учитывая необходимую точность получаемого результата.
В результате освоения дисциплины Вы должны знать:
методы хранения чисел в памяти ЭВМ и действия над ними, оценку точности вычислений, т.е. действия над приближенными числами;
методы решения основных математических задач – интегрирования, дифференцирования, решения линейных и трансцендентных уравнений и систем уравнений с помощью ЭВМ.
В результате освоения дисциплины у Вас должны формироваться общие компетенции (ОК):
Название ОК
Результат, который Вы должны получить после изучения содержания дисциплины
ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
Понимание роли математического аппарата программировании
ОК 2. Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
Умения применять математический аппарат в решении профессиональных задач, оценивать их эффективность и качество
ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.
Развитие аналитического мышления.
ОК 4. Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.
Умение ориентироваться в многообразии моделей объектов естествознания и методов их решения
ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.
Умение осуществлять поиск нужной информации различных источниках.
ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.
Умение эффективно распределять объём работы между участниками решения конкретной задачи.
ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.
Навыки доводить решение поставленной задачи до получения нужного результата и его интерпретация.
ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
Расширение круга представлений о возможности применения математического аппарата для решения общепрофессиональных задач.
ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.
Умение составлять математические модели содержательных задач и применять для их решения численные методы.
Содержание дисциплины поможет Вам подготовиться к последующему освоению профессиональных компетенций в рамках профессионального МДК 01.02 Прикладное программирование, входящего в ПМ.01 Разработка программных модулей программного обеспечения компьютерных систем.
В таблице приведены профессиональные компетенции, к освоению которых готовит содержание дисциплины.
Название ПК
Результат, который Вы должны получить после изучения содержания дисциплины
ПК 1.7.в Осуществлять разработку кода программного продукта для решения вычислительных задач, учитывая необходимую точность получаемого результата.
Умение использовать алгоритмы численных методов при составлении программ
ПКв Реализовывать основные численные подходы к решению математических задач при работе в базе данных;
Умение использовать алгоритмы численных методов при составлении программ
ПКв Осуществлять разработку тестовых сценариев при решения основных математических задач.
Умение использовать алгоритмы численных методов при составлении программ
Внимание! Если в ходе изучения дисциплины у Вас возникают трудности, то Вы всегда можете к преподавателю прийти на дополнительные занятия, которые проводятся согласно графику. Время проведения дополнительных занятий Вы сможете узнать у преподавателя, а также познакомившись с графиком их проведения, размещенном на двери кабинета преподавателя.
В случае, если Вы пропустили занятия, Вы также всегда можете прийти на консультацию к преподавателю в часы дополнительных
занятий.
ОБРАЗОВАТЕЛЬНЫЙ МАРШРУТ ПО ДИСЦИПЛИНЕ
Таблица 1
Формы отчетности, обязательные для сдачи
Количество
практические занятия
10
Итоговая аттестация (при наличии)
экзамен
Желаем Вам удачи!
СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
ВВЕДЕНИЕ
Этапы решения прикладной задачи и классификация ошибок.
1. Этапы решения прикладной задачи и классификация ошибок
Основной задачей численных методов является анализ ошибок (погрешностей), возникающих при решении прикладных задач.
Часть этих погрешностей связана с вычислениями, которые в наше время производятся на ЭВМ.
Возникновение, накопление и распространение ошибок проходят через все стадии решения прикладной задачи, начиная с получения значений исходных данных. В достаточно общем случае процесс решения задач с использованием ЭВМ состоит из следующих этапов:
постановка задачи и построение математической модели (этап моделирования);
выбор метода и разработка алгоритма (этап алгоритмизации);
запись алгоритма на языке, понятном ЭВМ (этап программирования);
отладка и исполнение программы на ЭВМ (этап реализации);
анализ полученных результатов (этап интерпретации).
Рассмотрим подробнее каждый из этапов.
Постановка задачи изначально связана не с идеальными, а с реальными объектами – производственными процессами и явлениями природы, физическими закономерностями, экономическими отношениями и т.д. Точную формулировку условий и целей решения называют математической постановкой задачи. Выделяя наиболее существенные свойства реального объекта, исследователь описывает их с помощью математических соотношений. Этот этап называют моделированием.
Построение модели является наиболее сложным и ответственным этапом решения. Модель может иметь вид уравнения, системы уравнений или быть выраженной в форме иных, как угодно сложных, математических структур или соотношений самой различной природы.
Вслед за построением математической модели исследователь разрабатывает метод решения задачи и составляет алгоритмы. Этап поиска и разработки алгоритма решения задачи в рамках заданной математической модели называют алгоритмизацией. На этом этапе могут использоваться любые подходящие средства представления алгоритмов: словесные описания, формулы, схемы и т.п.
На следующем этапе алгоритм задачи записывается на языке, понятном ЭВМ. ЭТО – этап программирования.
После отладки и тестирования программы следует этап реализации – исполнение программы ЭВМ и получение результатов решения.
Завершающий этап решения задачи – это анализ, или интерпретация результатов. На этом этапе происходит осмысление полученных результатов, сопоставление их с результатами контрольного просчета, а также с данными, полученными экспериментальным путем.
В условиях использования ЭВМ численные методы выступают как мощное математическое средство решения практических задач. При этом важно иметь в виду, что сам по себе фактор использования ЭВМ не упрощает, а в некотором смысле даже усложняет оценку точности полученных результатов.
Контрольные вопросы
Из каких основных этапов состоит процесс решения задачи с помощью ЭВМ?
Дайте характеристику каждого этапа.
Раздел 1. Действия над приближенными числами
Лекция 1:
«Приближенное значение величины. Погрешности арифметических действий»
План лекции
Приближенные числа. Погрешности приближенных значений чисел.
Верные цифры числа.
Относительная погрешность приближенного значения числа.
Вычисление погрешности арифметических действий.
Оценка погрешностей значений функции.
Приближение числа. Погрешности приближённых значений чисел
Пусть X-точное значение некоторой величины, x - наилучшее приближение этой величины.
Определение: Абсолютной погрешностью ех приближенного значения числа Х называется модуль разности между точным числом Х и его приближенным значением х, т.е.
ех = (Х-х(.
Определение: Число х называется приближённым значением точного числа Х с точностью до (х, если абсолютная погрешность приближённого значения х не превышает (х, т.е.
(Х-х (( (х . (1.1)
Определение: Число (х называется границей абсолютной погрешности приближённого значения числа х.
Число (х на практике стараются подобрать как можно меньше и простое по записи.
Из неравенства (1.1) найдём границы, в которых заключено точное значение числа Х:
х - (х ( Х ( х + (х.
НГх= х - (х - нижняя граница приближения величины Х.
ВГх= х +(х - верхняя граница приближения величины Х.
Пример: Даны приближённые значения числа Х =2/3, х13 EMBED Equation.3 1415= 0,6, х13 EMBED Equation.3 1415=0,66, х13 EMBED Equation.3 1415=0,67. Какое из трёх приближений является лучшим?
Решение: Вычислим абсолютные погрешности приближений:
ех1 =(2/3- 0,6(=13 EMBED Equation.3 1415; ех2 =(2/3- 0,66(=13 EMBED Equation.3 1415; ех3 =(2/3- 0,67(=13 EMBED Equation.3 1415.
Так как величина ех3 является наименьшей из трех просчитанных, то наилучшим приближением числа Х = 2/3 является х13 EMBED Equation.3 1415=0,67.
Верные цифры числа
Определение: Цифра m приближенного числа х, называется верной в широком смысле, если граница абсолютной погрешности числа х не превосходит единицы того разряда, в котором записывается цифра m.
В числах, полученных в результате измерений или вычислений и используемых при расчетах в качестве исходных данных, а также в десятичной записи приближенного значения числа, все цифры должны быть верными.
Пример: Указать верные цифры следующих чисел:
а) 13 EMBED Equation.3 1415; б) 13 EMBED Equation.3 1415.
Решение: а) Граница погрешности (х =0,056 не превосходит единицы разряда десятых (0,056<0,1). Значит, верными являются цифры 3 и 7.
б) Так как (х =0,0008<0,001, то все цифры приближенного числа 3,627 верны.
Определение: Цифры в записи приближенного числа, о которых неизвестно, являются ли они верными, называют сомнительными.
Определение: Значащими цифрами приближенного числа называются все его верные цифры, кроме нулей, стоящих перед первой цифрой (слева направо), отличной от нуля.
Пример: 0,2409 – четыре значащие цифры; 24,09 - четыре значащие цифры; 100,700 - шесть значащих цифр.
Выдача числовых значений ЭВМ, как правило, устроена таким образом, что нули в конце записи числа, даже если они верные, не сообщаются.
В процессе вычислений часто происходит округление чисел, т.е. замена чисел их значениями с меньшим количеством значащих цифр.
Относительная погрешность приближенного значения числа
Определение: Относительной погрешностью 13 EMBED Equation.3 1415 приближенного числа х числа Х называется отношение абсолютной погрешности (х этого приближения к числу х, т.е.
13 EMBED Equation.3 1415 (1.2)
Чем меньше относительная погрешность числа, тем выше качество измерений или вычислений.
Если первая значащая цифра в относительной погрешности 13 EMBED Equation.3 1415 меньше 5, то граница относительной погрешности определяется из неравенства 13 EMBED Equation.3 1415 (1.3), где n- количество верных цифр.
Заключение:
При решении задач погрешность вызывается тремя причинами:
Неопределенность при задании входных данных, которая приводит к неопределенности в ответе. Ответ может быть указан лишь с погрешностью, которая называется неустранимой.
При фиксированных входных данных ответ вычисляется с помощью приближенного метода. Такая погрешность называется погрешностью метода вычислений.
Выбранный метод решения реализуется неточно из-за ошибок округления при вычислениях. Такая погрешность называется погрешностью округления.
Вычисление погрешностей арифметических действий
Задача: Имеются приближённые данные с известными оценками погрешностей. С данными производится арифметическая операция. Какое влияние на погрешность результата оказывают погрешности исходных данных?
Сложение и вычитание:
Абсолютная погрешность алгебраической суммы приближенных значений не превышает суммы абсолютных погрешностей этих значений:
13 EMBED Equation.3 1415(x+y) (13 EMBED Equation.3 1415x+13 EMBED Equation.3 1415y.
Вычислим относительные погрешности суммы и разности, пользуясь формулой (1.2):
13 EMBED Equation.3 141513 EMBED Equation.3 1415 ;
13 EMBED Equation.3 1415.
Пример: x = 62,425, y = 62,409. Найти разность и погрешность разности.
Решение: Имеем х-у = 62,425-62,409 = 0,016.
Граница абсолютной погрешности разности: 13 EMBED Equation.3 1415, поэтому в числе 0,016 только 2 верные цифры (следовательно, можно было округлить до сотых). Сравним погрешности результата и исходных данных:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Таким образом, в данном случае относительная погрешность разности оказалась почти в 8000 раз больше относительной погрешности исходных данных.
2) Умножение и деление:
Принимая во внимание свойства логарифмов: ln(xy)=lnx+lny,
ln(x/y) =lnx-lny и приближённую формулу 13 EMBED Equation.3 1415, имеем:
13 EMBED Equation.3 1415, (знак «±» не влияет величину погрешности),
13 EMBED Equation.3 1415
Таким образом, абсолютные погрешности произведения и частного:
13 EMBED Equation.3 1415
Пример: x=43,1, y=5,72. Найти частное и погрешность результата.
Решение: Найдем частное 13 EMBED Equation.3 1415
Найдём число верных цифр результата, для этого вычислим
13 EMBED Equation.3 1415 частное имеет одну верную цифру. Округляя полученный результат с одной запасной цифрой, получим 13 EMBED Equation.3 1415.
Для удобства все формулы для вычисления погрешностей арифметических действий сведем в общую таблицу (таб.1.1).
Таблица 1.1
х#у
·(х#у)
·(х#у)
х+у
13 EMBED Equation.3 1415x+13 EMBED Equation.3 1415y
13 EMBED Equation.3 1415
х-у
13 EMBED Equation.3 1415x+13 EMBED Equation.3 1415y
13 EMBED Equation.3 1415
ху
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
х/у
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Оценка погрешностей значений функций
Вычисления по формулам нередко предполагают нахождение значений различных математических функций. При нахождении значения функции с помощью МК или компьютера, функция преобразуется к стандартным. Какая погрешность при этом допускается?
Пусть функция f(x) дифференцируема в некоторой окрестности точки х.
Пусть ех - абсолютная погрешность аргумента, тогда абсолютная погрешность функции
еf 13 EMBED Equation.3 1415.
Так как погрешность ех очень мала по сравнению с аргументом х, воспользуемся равенством: 13 EMBED Equation.3 1415. Заменим ех на 13 EMBED Equation.3 1415. Тогда можно записать формулы для вычисления абсолютных погрешностей значений некоторых функций одной переменной (таб.1.2)
Таблица 1.2
f(x)
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equ
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·–
·
·
·
·
·on.3 1415
arctg x
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Пример: Пусть х=0,8, причем 13 EMBED Equation.3 1415x=0,05, т.е. все цифры в числе верны. Вычислить значение sinx.
Решение: С помощью МК получаем sin0,8 =0,717356091. Для определения верных цифр в результате оценим его абсолютную погрешность: 13 EMBED Equation.3 1415, отсюда следует, что в полученном значении sin0,8 имеет лишь одну верную цифру .Округляя результат с одной запасной цифрой, получим sin0,8=0,72.
Контрольные вопросы
Что такое абсолютная погрешность приближенного значения величины?
Что такое относительная погрешность приближенного значения величины?
Какие цифры в записи приближенного числа называются верными в широком смысле? Как определить количество верных цифр числа?
Какие цифры в записи приближенного числа называются значащими? Как определить количество значащих цифр числа?
Какое влияние на погрешность арифметических действий оказывают погрешности исходных данных?
В какой зависимости находится абсолютная погрешность значения функции одной переменной от абсолютной погрешности значения аргумента?
Лекция 2
«Способы приближенных вычислений по заданной формуле»
План лекции
Способы приближенных вычислений по заданной формуле. Вычисление по правилам подсчета цифр.
Вычисление со строгим учётом предельных абсолютных погрешностей.
Вычисление по методу границ.
Наиболее распространенный вид вычислений – это вычисления по готовой формуле. В компьютере вычисление при любой громоздкости формулы обеспечивается, как правило, одной командой. Если при этом программно не предусматривается контроль вычислительных погрешностей, вычислитель анализирует результат в конце счета. Иногда условия вычислительной задачи заставляют вести пооперационный учет движения вычислительной погрешности. При этом сохраняется возможность получить достоверный окончательный результат методом его итогового округления.
Рассмотрим приемы вычислений, учитывающие как пооперационную, так и итоговую методику оценки точности.
Вычисление по правилам подсчета цифр
При вычислении данным методом явного учёта погрешностей не ведётся, Правила подсчёта цифр показывают лишь, какое количество значащих цифр или десятичных знаков в результате можно считать надёжными.
Правила метода:
При сложении и вычитании приближенных чисел следует считать верными столько десятичных знаков после запятой, сколько их в приближенном данном с наименьшим числом знаков после запятой.
При умножении и делении приближенных чисел нужно выбрать число с наименьшим количеством значащих цифр и округлить остальные числа так, чтобы в них было лишь на одну значащую цифру больше, чем в наименее точном числе.
При определении количества верных цифр в значениях функций от приближённых значений аргумента следует грубо оценить значение модуля производной функции. Если это значение не превосходит единицы или близко к ней, то в значении функции можно считать верными столько знаков после запятой, сколько их имеет значение аргумента. Если же модуль производной функции превосходит единицу, то количество верных десятичных знаков в значении функции меньше, чем в аргументе на величину, равную разряду оценки производной.
В записи промежуточных результатов следует сохранять на одну цифру больше, чем описано в правилах 1-3. В окончательном результате эта запасная цифра округляется.
Правила подсчёта цифр носят оценочный характер, но практическая надёжность этих правил достаточно высока.
При исследовании данного метода используется расчётная таблица – расписка формул.
Пример: Вычислить значение функции 13 EMBED Equation.3 1415, а = 2,156, b = 0,927.
Решение: Пошаговые вычисления для удобства будем проводить в таблице, в правом столбце, которой записываем пояснения.
Таблица 2.1
а
2,156
пояснения при подсчете верных цифр
b
0,927
13 EMBED Equation.3 1415
8,637
13 EMBED Equation.3 1415 = 8,63652,
оценим производную (13 EMBED Equation.3 1415)’ = 13 EMBED Equation.3 1415, значит (используя правило 3), надо сохранить на один знак меньше, чем в значении аргумента + 1 запасная цифра.
13 EMBED Equation.3 1415
0,9628
13 EMBED Equation.3 1415 = 0,9628083,
оценим производную 13 EMBED Equation.3 1415, (используя правило 3) сохраняем три цифры как в аргументе + 1 запасная цифра.
13 EMBED Equation.3 1415+13 EMBED Equation.3 1415
9,600
13 EMBED Equation.3 1415+13 EMBED Equation.3 1415=8,637+0,9628=9,5998,
(по правилу 1)результат округляется до трёх знаков после запятой, т.е. 9,600.
13 EMBED Equation.3 1415
0,8593
13 EMBED Equation.3 1415,
(по правилу 2) результат округляем до трех цифр, как аргумент + 1 запасная цифра.
13 EMBED Equation.3 1415
3,0153
13 EMBED Equation.3 1415,
(используя правило 1)округляем результат до трех цифр + 1 запасная цифра.
13 EMBED Equation.3 1415
1,1037
13 EMBED Equation.3 1415,
оценим производную 13 EMBED Equation.3 1415, (используя правило 3) сохраняем три цифры как в аргументе + 1 запасная цифра.
A
8,698
13 EMBED Equation.3 1415,
при округлении результата использовали правило 2.
А
8,70
8-запасная цифра,
По правилу 4, запасная цифра в окончательном результате округляется 13 EMBED Equation.3 1415
Вычисление со строгим учётом предельных абсолютных погрешностей
Этот метод предусматривает использование правил вычисления предельных абсолютных погрешностей. При пооперационном учете ошибок промежуточные результаты, так же как и их погрешности, заносятся в специальную таблицу, состоящую из двух параллельно заполняемых частей – для результатов и их погрешностей. В таблице приведены пошаговые вычисления со строгим учетом предельных абсолютных погрешностей по той же формуле, что и в предыдущем примере, и в предположении, что исходные данные a и b имеют предельные абсолютные погрешности 13 EMBED Equation.3 1415(по формуле 1.3), т.е. у a и b все цифры верны.
Промежуточные результаты вносятся в таблицу после округления до одной запасной цифры; значения погрешностей для удобства округляются (с возрастанием!) до двух значащих цифр. Проследим ход вычислений на одном этапе.
Пример: Вычислить значение функции 13 EMBED Equation.3 1415, а = 2,156, b = 0,927.
Решение: Все вычисления также проведем в таблице. Вычисляем значение функции в заданной точке и погрешность результата.
Таблица 2.2
а
b
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415+13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
a+13 EMBED Equation.3 1415
ln(a+13 EMBED Equation.3 1415)
A
2,156
0,927
8,637
0,9628
9,603
0,860
3,016
1,104
8,70
13 EMBED Equation.3 1415 а
13 EMBED Equation.3 1415 b
13 EMBED Equation.3 1415(13 EMBED Equation.3 1415)
13 EMBED Equation.3 1415(13 EMBED Equation.3 1415)
13 EMBED Equation
·
·
·–
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Используя калькулятор, имеем 13 EMBED Equation.3 1415.
При вычислении предельных абсолютных погрешностей используем таблицу 1.2.
13 EMBED Equation.3 1415.
Судя по ее величине, в полученном значении экспоненты в строгом смысле верны два знака после запятой. Округляем это значение с одной запасной цифрой:13 EMBED Equation.3 1415 и вносим его в таблицу.
При этом возникает погрешность округления: 8,637-8,63652=0,00048.
Вслед за этим вычисляем полную погрешность полученного результата (погрешность действия плюс погрешность округления: 0,0044+0,00048=0,0049), которую так же вносим в таблицу.
Все последующие действия выполняем аналогично с применением соответствующих формул для предельных абсолютных погрешностей.
Округляя окончательный результат до последней верной в строгом смысле цифры, а так же округляя погрешность до соответствующих разрядов результата, окончательно получаем: А = 8,7 13 EMBED Equation.3 14150,1.
Вычисления по методу строго учёта предельных абсолютных погрешностей можно выполнить на компьютере с помощью программы. Если не производить пооперационного учёта движения вычислительной ошибки, то достаточно вычислить значение предельной абсолютной погрешности окончательного результата, а затем произвести его округление.
Вычисление по методу границ
Если нужно иметь абсолютно гарантированные границы возможных значений вычисляемой величины, используют специальный метод вычислений – метод границ.
Пусть f(x, y) – функция непрерывная и монотонная в некоторой области допустимых значений аргументов x и y. Нужно получить её значение f(a, b), где a и b – приближенные значения аргументов, причем достоверно известно, что
13 EMBED Equation.3 1415; 13 EMBED Equation.3 1415.
Здесь НГ, ВГ - обозначение соответственно нижней и верхней границ значений параметров. Итак, вопрос состоит в том, чтобы найти строгие границы значения f(a, b) при известных границах значений a и b.
Допустим, что функция f(x, y) возрастает по каждому из аргументов x и y. Тогда
13 EMBED Equation.3 1415.
Пусть теперь f(x, y) возрастает по аргументу x и убывает по аргументу y. Тогда будет строго гарантировано неравенство
13 EMBED Equation.3 1415.
Рассмотрим указанный принцип на примере основных арифметических действий. Пусть 13 EMBED Equation.3 1415. Тогда очевидно, что
13 EMBED Equation.3 1415.
Точно так же для функции 13 EMBED Equation.3 1415(она по x возрастает, а по y убывает) имеем
13 EMBED Equation.3 1415.
Аналогично для умножения и деления:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Рассмотрим функцию13 EMBED Equation.3 1415. Замечаем, что при увеличении x она убывает, а с увеличением y – возрастает. Следовательно, имеет место неравенство
13 EMBED Equation.3 1415.
Вычисляя по методу границ с пошаговой регистрацией промежуточных результатов, удобно использовать обычную вычислительную таблицу, состоящую из двух строк – отдельно для вычисления НГ и ВГ результата (по этой причине метод границ называют ещё методом двоичных вычислений). При выполнении промежуточных вычислений и округлении результатов используются все рекомендации правил подсчёта цифр с одним важным дополнением: округление нижних границ ведётся по недостатку, а верхних - по избытку. Окончательные результаты округляются по этому же правилу до последней верной цифры.
Пример: Вычислить значение функции 13 EMBED Equation.3 1415, а = 2,156, b = 0,927.
Решение: Нижняя и верхняя границы значений a и b определены из условия, что в исходных данных: а = 2,156 и b = 0, 927, все цифры верны (13 EMBED Equation.3 1415,
т.е. 2,1555 < a < 2,1565; 0,9265 < b < 0,9275.
Таблица 2.3
а
b
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415+13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
a+13 EMBED Equation.3 1415
ln(a+13 EMBED Equation.3 1415)
A
НГ
2,1555
0,9265
8,63220
0,96255
9,59475
0,85840
3,01434
1,10338
8,6894
ВГ
2,1565
0,9275
8,64084
0,96307
9,60391
0,86026
3,01676
1,10419
8,7041
Таким образом, результат вычислений значения А по методу границ имеет вид
8,6894 < А < 8,7041.
По результатам вычислений получаем
13 EMBED Equation.3 1415
что дает А = 8,69713 EMBED Equation.3 14150,008, или при записи верными цифрами, А=8,713 EMBED Equation.3 14150,01.
Контрольные вопросы
Как формулируются правила подсчета цифр?
Какова последовательность действий на каждом промежуточном этапе расчетной таблицы в вычислениях по правилам подсчета цифр с пооперационным учетом ошибок? на заключительном этапе?
Как оформляются вычисления со строгим учетом предельных погрешностей при пооперационном учете ошибок?
Какова последовательность действий на каждом промежуточном этапе расчетной таблицы в вычислениях по методу строгого учета предельных погрешностей с пооперационным учетом ошибок? на заключительном этапе?
Как вычисляются предельные погрешности результата при использовании методики итоговой оценки ошибки вычислений?
В чем основное отличие метода границ от вычислений по методу строгого учета границ погрешностей?
Какова последовательность действий на каждом промежуточном этапе расчетной таблицы в вычислениях по методу границ с пооперационным учетом ошибок? на заключительном этапе?
Задачи
Вычислите с помощью МК значение величины Z при заданны значениях параметров a, b и c, использую «ручные» расчетные таблицы для пошаговой регистрации результатов вычислений, тремя способами:
по правилам подсчета цифр;
с систематическим учетом границ абсолютных погрешностей;
по способу границ.
Сравните полученные результаты между собой, прокомментируйте различие методов вычислений и смысл полученных числовых значений.
№
Z
a
b
c
1
13 EMBED Equation.3 1415
0,038
3,9353
5,75
2
13 EMBED Equation.3 1415
0,11587
4,25
3,00971
3
13 EMBED Equation.3 1415
82,3574
34,1
7,00493
Практические занятия
Практическое занятие №1 «Использование основных численных методов решения математических задач. Вычисление погрешностей результатов арифметических действий»
Раздел 2. Численные методы решения основных математических задач
Тема 2.1. Решение линейных и трансцендентных уравнений с помощью ЭВМ
Лекция 3
«Метод половинного деления решения алгебраических и трансцендентных уравнений»
План лекции
Постановка задачи решения уравнений.
Отделение корней алгебраических и трансцендентных уравнений.
Метод половинного деления решения алгебраических и трансцендентных уравнений.
Пример решения алгебраических и трансцендентных уравнений методом половинного деления.
Постановка задачи решения уравнений
Решение уравнений – одна из древнейших математических проблем. Не счесть приложений математики, в которых решение уравнений является необходимым элементом решения задачи.
Примеры уравнений, позволяющих получат аналитические решения, хорошо известны из школьной математики. Тем не менее, подавляющее большинство уравнений, встречающихся в приложениях, не могут быть решены аналитически. Тогда применяются численные методы решения уравнений, которые являются более мощными.
Часто аналитические методы решения уравнений называют «точными», а численные – «приближенными». Действительно, численные методы практически всегда дают приближенный результат, но если необходимо довести решение «до числа», то часто и аналитические методы в реальности позволяют получить лишь приближенный результат.
Пусть имеется уравнение вида
f(x)=0 , (2.1)
где f(x) - алгебраическая или трансцендентная функция.
Решить такое уравнение – значит установить, имеет ли оно корни, сколько корней, и найти значения корней (с указанной точностью). Ограничимся обсуждением методов поиска лишь действительных корней, не затрагивая проблему корней комплексных.
Отделение корней алгебраических и трансцендентных уравнений
Решение указанной задачи начинается с отделения корней, т.е. с установления:
количества корней;
наиболее «тесных» промежутков, каждый из которых содержит только один корень.
Следует отметить, что универсальных приемов решения этой задачи, пригодных для любых уравнений, не существует.
Если бы мы располагали графиком функции f(x), то примерное положение корней уравнения (2.1) было бы очевидным – точки пересечения графика с осью абсцисс. Однако построение графиков функций обычно и начинается с поиска ее нулей, т.е. возникает замкнутый круг.
Тем не менее, отделение корней во многих случаях можно произвести графически.
Упростим задачу, заменив уравнение (2.1) равносильным ему уравнением
f1(x)= f2(x). (2.2)
В этом случае строятся графики функций f1(x) и f2(x), а потом на оси х отмечаются отрезки, локализующие абсциссы точек пересечения этих графиков.
При решении задачи об отделении корней бывают полезными следующие очевидные положения:
Если непрерывная на отрезке [a;b] функция f(x) принимает на его концах значения разных знаков (т.е. f(a). f(b)<0), то уравнение (2.1) имеет на этом отрезке, по меньшей мере, один корень.
Если функция f(x) к тому же еще и монотонна, то корень на отрезке [a;b] единственный.
Пример: Для графического отделения корней уравнения 13 EMBED Equation.3 1415 преобразуем его к равносильному уравнению 13 EMBED Equation.3 1415 и отдельно построим графики функций 13 EMBED Equation.3 1415.
Из графика вполне очевидно, что уравнение имеет единственный корень
· и этот корень находится на отрезке [1;1,5].
Вычислим для проверки значения функции 13 EMBED Equation.3 1415на концах отрезка [1;1,5]: f(1)=0.909298; f(1,5)= -0,264344. Как видно, корень на отрезке [1;1,5] действительно имеется.
Рассмотренный прием позволяет при желании сузить отрезок, полученный графическим способом.
Так, в нашем примере, имеем f(1,3)=0,253138>0, так что отрезком, на котором находится корень, можно считать[1,3;1,5].
Для уточнения корней можно пользоваться различными методами. Рассмотрим некоторые из них.
Метод половинного деления
Пусть уравнение (2.1) имеет на отрезке [a;b] единственный корень, причем функция f(x) на этом отрезке непрерывна. Разделим отрезок [a;b] пополам точкой с=(a+b)/2. Если f(c)
·0(что практически наиболее вероятно), то возможны два случая: f(x) меняет знак либо на отрезке [a;с] (рис 2.1), либо на отрезке [с;b] (рис 2.2).
Рис 2.1. – функция f(x) меняет знак на отрезке [a;c] Рис 2.2. – функция f(x) меняет знак на
отрезке [c;b]
Выбирая в каждом случае тот из отрезков, на котором функция меняет знак, и продолжая процесс половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения.
Метод половинного деления требует утомительных ручных вычислений, однако он легко реализуется с помощью программы на компьютере.
Пример решения уравнений методом половинного деления
Пример: Найти корень уравнения 13 EMBED Equation.3 1415 на отрезке [1,3;1,5] с точностью до 10-4.
Решение: Уравнение 13 EMBED Equation.3 1415 имеет единственный корень на отрезке [1,3;1,5] (см.лекцию 2).
Уточним корень уравнения: Найдем середину отрезка [1,3;1,5]: 13 EMBED Equation.3 1415.
Определим, на каком из полученных отрезков [1,3;1,4] и [1,4;1,5] функция 13 EMBED Equation.3 1415меняет свой знак.
1) [1,3;1,4]: 13 EMBED Equation.3 1415
2) [1,4;1,5]: 13 EMBED Equation.3 1415
Значит, корень уравнения находится на отрезке [1,3;1,4].
Проверим, достигается ли заданная точность решения 10-4:
13 EMBED Equation.3 1415, точность не достигнута.
Разделим отрезок [1,3;1,4] пополам точкой 13 EMBED Equation.3 1415.
Определим, на каком из полученных отрезков [1,3;1,35] и [1,35;1,4] функция 13 EMBED Equation.3 1415меняет свой знак.
1) [1,3;1,35]: 13 EMBED Equation.3 1415
2) [1,35;1,4]: 13 EMBED Equation.3 1415
Значит, корень уравнения находится на отрезке [1,35;1,4].
Проверим, достигается ли заданная точность решения 10-4:
13 EMBED Equation.3 1415, точность не достигнута.
Снова разделим отрезок [1,35;1,4] пополам точкой 13 EMBED Equation.3 1415.
Определим, на каком из полученных отрезков [1,35;1,375] и [1,375;1,4] функция 13 EMBED Equation.3 1415меняет свой знак.
1) [1,35;1,375]: 13 EMBED Equation.3 1415
2) [1,375;1,4]: 13 EMBED Equation.3 1415
Значит, корень уравнения находится на отрезке [1,375;1,4].
Проверим, достигается ли заданная точность решения 10-4:
13 EMBED Equation.3 1415, точность не достигнута.
Продолжая делить отрезок пополам и проверять знаки функции на новых промежутках, до тех пор, пока не будет достигнута нужная точность решения (сделайте самостоятельно), получим:
Решение уравнения с точностью 10-4: х=1,3994.
Контрольные вопросы
Что означает «решить уравнение аналитически» и «решить уравнение численно»?
В чем заключается задача отделения корней?
В чем состоит основная идея метода половинного деления?
Может ли метод половинного деления дать точное значение корня уравнения?
Лекция 4
«Метод хорд и касательных решения алгебраических и трансцендентных уравнений»
План лекции
Метод касательных решения алгебраических и трансцендентных уравнений.
Пример решения алгебраических и трансцендентных уравнений методом касательных.
Метод хорд решения алгебраических и трансцендентных уравнений.
Пример решения алгебраических и трансцендентных уравнений методом хорд.
Метод касательных
Наряду с методом половинного деления существуют и другие, более сложные и более эффективные итерационные методы. Прежде всего, к ним относится группа методов, которые связаны с именем Ньютона. Рассмотрим два из них – метод касательных и метод хорд.
Оба метода основаны на следующем приеме.
Пусть уравнение (2.1) имеет единственный корень на отрезке [a;b]. Преобразуем его к равносильному уравнению
13 EMBED Equation.3 1415 (2.3)
где13 EMBED Equation.3 1415 - любая функция, определенная на отрезке [a;b] и не обращающаяся на нем в нуль. Осуществляя различными способами выбор 13 EMBED Equation.3 1415, можно получить, в частности, и указанные методы.
Метод касательных. Пусть в (2.3) 13 EMBED Equation.3 1415. Таким образом, итерационная последовательность строится с помощью рекуррентного соотношения
13 EMBED Equation.3 1415 (2.4)
Функция f(x) удовлетворяет следующим условиям:
1) Является дважды дифференцируемой на отрезке [a;b];
2) Обе производные – первая и вторая – не меняют знак на этом отрезке, т.е. функция f(x) монотонна и не меняет характер выпуклости.
Таким образом, возможны четыре случая поведения функции f(x) в окрестности корня:
Рис 2.4 четыре возможности поведения функции f(x) в окрестности корня:
а - функция f(x) убывает и выпукла; в - функция f(x) возрастает и вогнута;
б - функция f(x) убывает и вогнута; г - функция f(x) возрастает и выпукла.
В такой ситуации за х0 берется тот конец отрезка [a;b], на котором функция f(x) и ее вторая производная имеют одинаковые знаки, т.е. выполняется условие 13 EMBED Equation.3 1415. Очевидно, что это левый конец [a;b] на рис 2.4, а и г и правый конец [a;b] на рис 2.4, б и в.
На каждом шаге построения итерационной последовательности буде проверять точность достижения корня с помощью неравенства:
13 EMBED Equation.3 1415. (2.5)
Рассмотренный метод называется методом касательных потому, что если обратиться к графической иллюстрации (рис 2.5), то точка х1, определяемая по формуле (2.4) при n=0, есть точка пересечения касательной, проведенной к графику y=f(x) в точке с абсциссой , определяемой предыдущим членом последовательности, с осью абсцисс.
Рис 2.5 геометрический смысл метода касательных
Каждому следующему члену итерационной последовательности (2.4) соответствует точка пересечения касательной, проведенной к графику y=f(x) в точке с абсциссой х0, с осью абсцисс.
2. Пример решения уравнений методом касательных
Пример: Уточнить корень уравнения 13 EMBED Equation.3 1415 на отрезке [1,3;1,5] методом касательных с точностью до 1.13 EMBED Equation.3 1415.
Решение: Формула (2.4) в нашем примере имеет вид
13 EMBED Equation.3 1415,
т.к . производная 13 EMBED Equation.3 1415.
Для определения точки 13 EMBED Equation.3 1415 найдем знаки 13 EMBED Equation.3 1415и 13 EMBED Equation.3 1415на концах отрезка [1,3;1,5]:
f (1, 3) = 0, 515501 - 0, 262363 = 0, 253137>0,
f (1, 5) = 0, 14112 - 0,405465 = - 0, 26435<0,
f” (1, 3) = -2,062 + 0,591716 = -1, 4703<0,
f” (1, 5) = -0, 56448 + 0, 4444 = - 0, 12<0.
Таким образом, 13 EMBED Equation.3 1415.
Вычислим несколько членов итерационной последовательности «ручным» способом:
13 EMBED Equation.3 1415
Сделаем проверку (2.5) для точности достижения корня:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415, значит 13 EMBED Equation.3 141513 EMBED Equation.3 1415
13 EMBED Equation.3 1415- требуемая точность не достигнута.
13 EMBED Equation.3 1415
Снова проверка:
13 EMBED Equation.3 1415- требуемая точность достигнута.
Корень уравнения х1= 1, 399429 .
3. Метод хорд
Реализуя метод касательных, при каждой итерации необходимо вычислить значение не только функции f(x), но и ее производной f’(х). Однако есть вариант метода Ньютона, в котором можно ограничиться вычислением только значений f(x), что иногда упрощает вычислительный алгоритм.
Если положить в (2.3) 13 EMBED Equation.3 1415, а в качестве с взять тот конец промежутка [a;b], на котором 13 EMBED Equation.3 1415, то приходим к итерационному методу:
13 EMBED Equation.3 1415, (2.6)
называемому методом хорд (или методом секущих).
В качестве х0 в этом случае следует принять тот конец промежутка [a;b], который остался после выбора с (т.е. если c=a, то x0=b или наоборот). Далее последовательность строится по формуле (2.6).
Оценка степени приближения к корню возможна с помощью неравенства (2.5).
На рисунке (2.6) проиллюстрирован геометрический смысл метода.
Рис 2.6 Геометрический смысл метода хорд
В данном случае c=b, x0=a, х1 соответствует точке пересечения хорды, соединяющей концы кривой, с осью абсцисс. Далее находится точка на кривой с абсциссой х1, проводится следующая хорда и т.д.
Пример решения уравнений методом хорд
Пример: Уточнить корень уравнения 13 EMBED Equation.3 1415 на отрезке [1,3;1,5] методом хорд с точностью до 1.13 EMBED Equation.3 1415.
Решение: Точка с выбирается так же, как и точка х0 в предыдущем примере, т.е. с=1,5. Будем приближать точку х0= а = 1, 3.
13 EMBED Equation.3 1415
Проверим, достигнута ли заданная точность.
13 EMBED Equation.3 1415- требуемая точность не достигнута.
Найдём следующее приближение:
13 EMBED Equation.3 1415
Проверим точность:
13 EMBED Equation.3 1415- требуемая точность достигнута
Итак, корень уравнения х=1, 39941.
Контрольные вопросы
Дайте общее описание метода касательных?
Дайте общее описание метода хорд?
Нарисуйте геометрические схемы методов касательных и хорд.
Запишите формулы для построения итерационных последовательностей для каждого метода.
Как проверяется требуемая точность в методах?
Задачи
Задание 1. Отделите корни заданного уравнения, пользуясь графическим методом.
Задание 2. По методу половинного деления вычислите один корень заданного уравнения с точностью 10-3.
Задание 3. Вычислите один корень заданного уравнения с точностью 10-3, используя метод хорд.
Задание 4. Вычислите один корень заданного уравнения с точностью 10-3, используя один из инструментальных пакетов.
Сопоставьте и прокомментируйте полученные результаты.
Уравнение
Пояснения
13 EMBED Equation.3 1415
-
13 EMBED Equation.3 1415
На отрезке [-1;1]
13 EMBED Equation.3 1415
-
Лекция 5
«Комбинированный метод хорд и касательных решения алгебраических и трансцендентных уравнений»
План лекции
Комбинированный метод хорд и касательных решения алгебраических и трансцендентных уравнений.
Пример решения алгебраических и трансцендентных уравнений комбинированным методом хорд и касательных.
Комбинированный метод хорд и касательных решения уравнений
Заметим, что метод хорд так же, как и метод касательных приближает корень исходного уравнения лишь с одной стороны, а с другой конец отрезка, содержащего корень, останется также неподвижным. Однако, в каждом из четырех случаев возможного поведения функции f(x) в окрестности корня, метод хорд и метод касательных приближает корень с разных сторон. Это позволяет применить для нахождения корня уравнения (2.1) комбинированный метод хорд и касательных, при котором на каждом шаге находится последующее приближение и по формуле (2.4) и по формуле (2.6).
При этом два новых приближения будут давать более узкий отрезок, на котором сохранится корень. Процесс сужения отрезка можно продолжать до достижения заданной точности, проверяемой по формуле (2.5).
2. Пример решения уравнений комбинированным методом хорд и касательных
Пример: Уточнить корень уравнения 13 EMBED Equation.3 1415 на отрезке [1,3;1,5] комбинированным методом хорд и касательных с точностью до 1.13 EMBED Equation.3 1415.
Предлагаем сделать пример самостоятельно, используя предыдущую лекцию.
Контрольные вопросы
Дайте общее описание комбинированного метода хорд и касательных?
Как проверяется требуемая точность в методе?
Задачи
Задание 1. Отделите корни заданного уравнения, пользуясь графическим методом.
Задание 2. По методу касательных вычислите один корень заданного уравнения с точностью 10-3.
Задание 3. Вычислите один корень заданного уравнения с точностью 10-4, используя комбинированный метод хорд и касательных.
Сопоставьте и прокомментируйте полученные результаты.
Уравнение
Пояснения
13 EMBED Equation.3 1415
-
13 EMBED Equation.3 1415
На отрезке [-1;1]
13 EMBED Equation.3 1415
-
Практические занятия
Практическое занятие №2 «Решение алгебраических и трансцендентных уравнений приближенными методами (метод половинного деления): разработка алгоритма и программы для решения вычислительных задач, учитывая необходимую точность получаемого результата»
Практическое занятие №3 «Решение алгебраических и трансцендентных уравнений приближенными методами (метод хорд и касательных): разработка алгоритма и программы для решения вычислительных задач, учитывая необходимую точность получаемого результата»
Тема 2.2. Решение систем уравнений с помощью ЭВМ
Лекция 6
«Метод Гаусса. Вычисление определителей методом Гаусса»
План лекции
Системы линейных алгебраических уравнений.
Метод Гаусса решения систем уравнений.
Вычисление определителей матриц.
Системы линейных алгебраических уравнений
Множество прикладных и чисто математических задач приводят к необходимости решения систем линейных алгебраических уравнений (С.Л.А.У). Без преувеличения можно утверждать, что это одна из важнейших задач вычислительной математики.
Значимость задачи породила целый ряд методов ее решения. Среди этих методов есть универсальные и специализированные (т.е. применимые лишь к системам, имеющим некоторые специальные свойства). Методы отличаются друг от друга эффективностью, требованиями к объемам машинной памяти (при реализации на ЭВМ), закономерностями накопления ошибок в ходе расчетов. Не существует одного метода, который можно было бы во всех случаях предпочесть всем остальным, и поэтому знакомство с некоторыми методами является обязательным для квалифицированного вычислителя.
Итак, перед нами система n линейных алгебраических уравнений с n неизвестными: 13 EMBED Equation.3 1415 (2.7)
Запись ее в такой форме достаточно громоздка. Будем использовать матричную форму записи, совершенно равносильную (2.7): AХ=B,
где 13 EMBED Equation.3 1415
Методы решения С.Л.А.У. вида (2.7) можно разделить на два класса: точные и итерационные.
К точным методам относятся:
1. метод определителей (метод Крамера), хорошо известный из курса линейной алгебры;
2. матричное решение: X=A-1В (если известна обратная матрица);
3. различные варианты метода исключения неизвестных (метод Гаусса).
Чаще всего такие методы реализуются на ЭВМ, и в процессе вычислений ошибки определения и погрешности арифметических действий неизбежны. В силу этого название «точный» не соответствует действительности.
К итерационным методам относятся приближённые методы решения С.Л.А.У., основанные на применении принципа сжимающих отображений (метод Зейделя, метод простой итерации).
Метод Гаусса решения систем уравнений
Под названием «метода Гаусса» фигурирует группа методов, объединенных идеей последовательного исключения неизвестных. Наиболее популярным является метод, основанный на так называемой схеме единственного деления; этот метод имеет также и ряд модификаций.
Сам по себе метод Гаусса относится к точным методам. Это означает, что если точно выполнять все требуемые действия, получено точное решение, поскольку погрешность метода в данном случае равна нулю.
Будем считать матрицу системы (2.7) невырожденной, т.е. ее определитель не равен нулю.
Рассмотрим алгоритм, который получил название схемы единственного деления.
Подвергнем систему (2.7) следующим преобразованиям.
Считая, что 13 EMBED Equation.3 1415(ведущий элемент), разделим на 13 EMBED Equation.3 1415 коэффициенты первого уравнения: 13 EMBED Equation.3 1415 (2.8)
Используя уравнение (2.8), легко исключить неизвестное x13 EMBED Equation.3 1415 из остальных уравнений системы (достаточно из каждого уравнения вычесть уравнение (2.8), умноженное на соответствующий коэффициент при x13 EMBED Equation.3 1415).
Над остальными уравнениями системы совершим аналогичное преобразование: выберем из их числа уравнение с ведущим элементом и исключим с его помощью из остальных уравнений неизвестные 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415
Повторяя этот процесс, получим систему с треугольной матрицей:
13 EMBED Equation.3 1415 (2.9)
Из системы (2.9) последовательно находим значения неизвестных 13 EMBED Equation.3 1415
Отметим, что последовательное исключение неизвестных называется прямым ходом метода Гаусса. Нахождение значений неизвестных – обратным ходом.
Пример: Решить систему линейных уравнений:
13 EMBED Equation.3 1415
Решение: Запишем расширенную матрицу системы:
13 EMBED Equation.3 1415
Так как, 13 EMBED Equation.3 1415, разделим элементы первой строки на 2,34. Затем из элементов второй строки вычтем элементы первой, умноженные на 8,04, а из элементов третьей - вычтем элементы первой, умноженные на 3,92.
13 EMBED Equation.3 1415.
Теперь элементы второй строки разделим на 19,685. И умножая их на (-0,938), вычтем из элементов третьей строки.
13 EMBED Equation.3 1415.
Элементы третьей строки, разделим на 29,732.
13 EMBED Equation.3 1415.
Получаем треугольную матрицу. Решая ее, начиная с последней строки, найдем значения неизвестных:
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415
Так как в процессе решения выполнялись округления, то решение содержит вычислительную ошибку.
Определение: Значение разностей между свободными элементами исходной системы и результатами подстановки в уравнения системы найденных значений неизвестных называется невязками.
В рассмотренном примере невязки имеют следующие значения:
13 EMBED Equation.3 1415
Следует заметить, что по величине невязок нельзя судить о погрешностях результатов, но можно уточнить решение системы, вычислив поправки для найденных значений неизвестных.
3. Вычисление определителей матриц
Приступая к рассмотрению процесса решения системы линейных уравнений методом Гаусса, делается оговорка, что система невырожденная, т.е. её определитель отличен от нуля.
Вычисление определителя может представлять и самостоятельный интерес, т.к. такая задача нередко встречается в высшей математике.
Рассмотрим алгоритм вычисления определителя в связи с решением с.л.а.у. методом Гаусса по схеме единственного деления.
Обозначим определитель системы через D.
Что происходит с ним на каждом шаге реализации метода Гаусса?
1) 13 EMBED Equation.3 1415;
2)13 EMBED Equation.3 1415;
n)13 EMBED Equation.3 1415.
Матрица коэффициентов при неизвестных системы, полученная в результате - треугольная, с единицами по главной диагонали. Поэтому её определитель равен 1.
Практический вывод:
Если необходимо вычислить определитель некоторой квадратной матрицы, надо решить систему уравнений с этой матрицей и произвольной правой частью и воспользоваться формулой:13 EMBED Equation.3 1415.
Контрольные вопросы
Какие методы решения с.л.а.у. вы знаете?
В чем заключается прямой и обратный ход в схеме единственного деления?
На чем основываются подходы к организации контроля вычислений в прямом ходе, обратном ходе?
На чем основываются алгоритмы вычисления определителя по методу Гаусса?
Задачи
Задание 1
Дана система трех линейных уравнений с тремя неизвестными:
13 EMBED Equation.3 1415
Решить систему методом Гаусса и
·спользуя «ручную» схему единственного деления:
расчеты выполняйте с тремя знаками после запятой (с применением калькулятора);
подставьте найденные решения в исходную систему, вычислите невязки и сравните полученные решения;
выбрав ведущие элементы схемы единственного деления, найдите значения определителя системы.
Задание 2
Решите систему, используя одно из инструментальных средств. Сопоставьте найденное решение с решениями, полученными при выполнении задания 1.
i
ai1
ai2
ai3
bi
1
2
3
0,78
0,02
0,12
-0,02
-0,86
0,44
-0,12
0,04
-0,72
0,56
0,77
1,01
1
2
3
0,66
1,54
1,42
0,44
0,74
1,42
0,22
1,54
0,86
-0,58
-0,32
0,83
1
2
3
3,43
74,4
3,34
4,07
1,84
94,3
-106,00
-1,85
1,02
46,8
-26,5
92,3
Лекция 7
«Применение метода Гаусса для вычисления обратной матрицы»
План лекции
Применение метода Гаусса для вычисления обратной матрицы.
Пример нахождения обратной матрицы методом Гаусса.
1. Применение метода Гаусса для вычисления обратной матрицы
Схема единственного деления может использоваться также и для вычисления элементов матрицы 13 EMBED Equation.3 1415, обратной для невырожденной матрицы A. По определению, 13 EMBED Equation.3 1415,где E – единичная матрица.
Представим искомую матрицу 13 EMBED Equation.3 1415и единичную матрицу Е в виде совокупности векторов-столбцов. В такой записи соотношение 13 EMBED Equation.3 1415 предстанет в виде совокупности из n систем линейных уравнений вида 13 EMBED Equation.3 1415.
Решение каждой системы дает соответствующий столбец обратной матрицы.
Расширив таблицу схемы единственного деления, можно проиллюстрировать получение обратной матрицы рассмотренным методом.
2. Пример нахождения обратной матрицы методом Гаусса
Пример: Дана матрица
13 EMBED Equation.3 1415
Найти обратную матрицу, пользуясь схемой единственного деления.
Решение:
Запишем данную и единичную матрицы в одну, и применим, к ним одновременно, элементарные преобразования схемы единственного деления:
13 EMBED Equation.3 1415
Так как, 13 EMBED Equation.3 1415, разделим элементы первой строки на 2,34. Затем из элементов второй строки вычтем элементы первой, умноженные на 8,04, а из элементов третьей - вычтем элементы первой, умноженные на 3,92.
13 EMBED Equation.3 1415.
Теперь элементы второй строки разделим на 19,685. И умножая их на (-0,938), вычтем из элементов третьей строки.
13 EMBED Equation.3 1415.
Элементы третьей строки, разделим на 29,732.
13 EMBED Equation.3 1415.
Из элементов второй строки вычтем элементы третьей, умноженные на 2,0401.
13 EMBED Equation.3 1415.
Из элементов первой строки вычтем элементы третьей, умноженные на (-4,9615).
13 EMBED Equation.3 1415.
Из элементов первой строки вычтем элементы второй, умноженные на (-1,7991).
13 EMBED Equation.3 1415.
Матрица, полученная справа и является искомой обратной матрицей:
13 EMBED Equation.3 1415.
Сделаем прямую проверку:
13 EMBED Equation.3 1415
Поскольку вычисления матрицы 13 EMBED Equation.3 1415велись с округлением, то наличие невязок, отражённых в матрице 13 EMBED Equation.3 1415, является естественным.
Контрольные вопросы
Каким образом схема единственного деления может использоваться для вычисления обратной матрицы?
Задачи
Задание 1
Дана система трех линейных уравнений с тремя неизвестными:
13 EMBED Equation.3 1415
Для матрицы системы, по схеме единственного деления, найдите обратную матрицу.
Задание 2
Решите систему, используя одно из инструментальных средств. Сопоставьте найденное решение с решениями, полученными при выполнении задания 1.
i
ai1
ai2
ai3
bi
1
2
3
0,78
0,02
0,12
-0,02
-0,86
0,44
-0,12
0,04
-0,72
0,56
0,77
1,01
1
2
3
0,66
1,54
1,42
0,44
0,74
1,42
0,22
1,54
0,86
-0,58
-0,32
0,83
1
2
3
3,43
74,4
3,34
4,07
1,84
94,3
-106,00
-1,85
1,02
46,8
-26,5
92,3
Лекция 8
«Метод итераций»
План лекции
Итерационные методы решения систем линейных уравнений. Метод простой итерации.
Пример решения систем линейных уравнений методом простой итерации.
1. Метод простой итерации
Как отмечалось ранее, итерационные методы используются для решения уравнений и систем любой природы. Рассмотрим, как это делается применительно к системам линейных алгебраических уравнений.
Приведём систему линейных алгебраических уравнений (2.7)
13 EMBED Equation.3 1415
к равносильной ей системе вида x=Ax:
13 EMBED Equation.3 1415 (2.10)
В сокращенной форме: 13 EMBED Equation.3 1415.
О системе (2.10) говорят, что она «приведена к нормальному виду».
Правая часть системы определяет отображение 13 EMBED Equation.3 1415 (2.11),
переводящее точку 13 EMBED Equation.3 1415 в точку 13 EMBED Equation.3 1415. Используя отображения (2.11) и выбрав начальную точку13 EMBED Equation.3 1415 можно построить итерационную последовательность точек.
Если отображение F является сжимающим, то эта последовательность сходится и её предел является решением системы (2.10) а, следовательно, и решением исходной системы (2.7).
Замечание: Отображение является сжимающим, если расстояние между образами меньше, чем расстояние между исходными точками.
Для отображения (2.11) необходимым и достаточным условием сжимаемости является следующее:
13 EMBED Equation.3 1415, (2.12),
т.е. максимальная из сумм модулей коэффициентов при неизвестных в правой части системы (2.10), взятых по столбцам, должен быть меньше 1.
Практическая схема решения с.л.у. методом простой итерации
С.л.у. (2.7) необходимо привести к нормальному виду (2.10).
Для обеспечения сходимости итерационной последовательности необходимо, чтобы коэффициенты 13 EMBED Equation.3 1415 при неизвестных в правой части системы были существенно меньше единицы.
Этого можно достичь, если исходную систему (2.7) с помощью равносильных преобразований привести к системе, у которой абсолютная величина коэффициентов, стоящих на главной диагонали, была больше абсолютных величин каждого из других коэффициентов, стоящих при неизвестных в соответствующих уровнях (такую систему называют системой с преобладающими диагональными коэффициентами). Если теперь разделить все уравнения на соответствующие диагональные коэффициенты и выразить из каждого уравнения неизвестное с коэффициентом, равным 1, будет получена система (2.10), у которой все 13 EMBED Equation.3 1415.
Для проверки точности решения используем условие (2.12).
2. Пример решения систем линейных уравнений методом простой итерации
Пример: Решить систему линейных уравнений
13 EMBED Equation.3 1415
методом простой итерации с точностью 13 EMBED Equation.3 1415.
Решение:
Построим систему с преобладающими диагональными коэффициентами.
В качестве 1-ого уравнения возьмем 2-ое, в качестве 3-его уравнения – 1-ое, в качестве 2-ого уравнения – сумму 1-го и 3-го уравнений:
13 EMBED Equation.3 1415
Разделим каждое из полученных уравнений на диагональный коэффициент и, выразим из каждого уравнения диагональные элементы:
13 EMBED Equation.3 1415
Проверку условия сходимости (2.12) и точности решения осуществим с помощью программы.
Контрольные вопросы
Каким образом система линейных уравнений преобразуется к итерационному виду?
Как сформулировать условие сходимости итерационного процесса
Как привести исходную систему линейных уравнений к системе с преобладающими диагональными элементами?
Постройте блок-схему решения системы линейных уравнений методом простой итерации.
Лекция 9
«Метод Зейделя»
План лекции
Итерационные методы решения систем линейных уравнений. Метод Зейделя.
Пример решения систем линейных уравнений методом Зейделя.
1. Метод Зейделя
Будем снова рассматривать систему линейных уравнений (2.7) и эквивалентную ей систему (2.10).
При решении системы (2.10) методом простой итерации каждый шаг итерационного процесса состоит в переходе от уже имеющегося приближения значений неизвестных к новому (очередному) приближению.
Обозначим элементы имеющегося приближения через 13 EMBED Equation.3 1415, а элементы очередного (вычисляемого) приближения через 13 EMBED Equation.3 1415 .
Вычислительные формулы имеют вид:
13 EMBED Equation.3 1415
Основная идея метода Зейделя состоит в том, что на каждом шаге итерационного процесса при вычислении значения 13 EMBED Equation.3 1415 учитываются уже полученные значения13 EMBED Equation.3 1415. Выпишем соответствующие вычислительные формулы:
13 EMBED Equation.3 1415
Справедливо следующее утверждение:
Если для матрицы коэффициентов системы (2.10) выполняется условие (2.12), то итерационный процесс метода Зейделя сходится к решению системы при любом выборе начального приближения 13 EMBED Equation.3 1415.
Преимущество этого метода состоит в том, что он обеспечивает более быструю сходимость, чем метод простой итерации.
2. Пример решения систем линейных уравнений методом Зейделя
Пример: Решить систему линейных уравнений
13 EMBED Equation.3 1415
методом Зейделя с точностью 13 EMBED Equation.3 1415.
Решение: Решение данного примера получим с помощью программы для компьютера.
Контрольные вопросы
В чем состоит отличие метода Зейделя от аналогичного процесса простой итерации?
Постройте блок-схему решения системы линейных уравнений методом Зейделя.
Практические занятия
Практическое занятие №4 «Решение систем линейных алгебраических уравнений методом Гаусса: разработка алгоритма и программы для решения вычислительных задач, учитывая необходимую точность получаемого результата»
Практическое занятие №5 «Решение систем линейных алгебраических уравнений приближенными методами: разработка алгоритма и программы для решения вычислительных задач, учитывая необходимую точность получаемого результата»
Тема 2.3. Интерполирование и экстраполирование функций
Лекция 10
«Интерполяция и экстраполяция. Интерполяционный многочлен Лагранжа»
План лекции
Постановка задачи аппроксимации функций.
Существование и единственность итерполяционного многочлена.
Интерполяционный многочлен Лагранжа.
1. Постановка задачи аппроксимации функций
В вычислительной математике нередки случаи, когда одну функцию приходится заменять другой, более другой и удобной для дальнейшей работы. Такую задачу называют аппроксимацией функций.
Поводом для аппроксимации функции может послужить, в частности, табличный способ её задания. Предположим, что результате некоторого эксперимента для конечного набора значений 13 EMBED Equation.3 1415 величины x из отрезка [a;b]: 13 EMBED Equation.3 1415
получен набор значений 13 EMBED Equation.3 1415 величины у (таблица 3.1).
таблица 3.1
x
x13 EMBED Equation.3 1415
x13 EMBED Equation.3 1415
x13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
F(x)
y13 EMBED Equation.3 1415
y13 EMBED Equation.3 1415
y13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Допустим, существует функциональная зависимость y=F(x).
Необходимо задать F(x) аналитически.
Точки 13 EMBED Equation.3 1415называют узлами аппроксимации.
Аппроксимация может быть необходима и когда функция трудновычисляемая или при вычислении определенных интегралов (13 EMBED Equation.3 1415 - по формуле Ньютона-Лейбница вычислен быть практически не может).
Классический подход к численному решению подобных задач заключается в том, чтобы, опираясь на информацию о функции F, по некоторому алгоритму подобрать аппроксимирующую функцию G, в определенном смысле «близкую» к F.
Чаще всего задача аппроксимации решается с помощью многочленов. Вычисления значений многочлена легко автоматизировать, производная и интеграл от многочлена, в свою очередь, также являются многочленами.
Для оценки «близости» функций выбирают тот или иной критерий согласия.
Для функций, заданных таблично, достаточно распространенным является критерий Чебышева, который определяет расстояние13 EMBED Equation.3 1415 между аппроксимируемой и аппроксимирующей функциями как максимум величины отклонения между этими функциями в узлах:
13 EMBED Equation.3 1415 (3.1)
Если 13 EMBED Equation.3 1415=0, т.е. 13 EMBED Equation.3 1415(в узлах значения совпадают), то соответствующий способ аппроксимации называют интерполяцией, а процедуру вычисления значений F(x) с помощью G(x) в точках, не являющихся узлами сетки, - интерполированием.
Часто процедура аппроксимации связана с другим критерием согласия:
13 EMBED Equation.3 1415.
Применяемый на его основе способ аппроксимации называется методом наименьших квадратов.
2. Существование и единственность интерполяционного многочлена
Пусть известны значения некоторой функции F(x):
x
x13 EMBED Equation.3 1415
x13 EMBED Equation.3 1415
x13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
F(x)
y13 EMBED Equation.3 1415
y13 EMBED Equation.3 1415
y13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Будем решать задачу интерполирования этой функции с помощью построения интерполяционного многочлена n-ой степени.
13 EMBED Equation.3 1415 (3.2)
который в узлах 13 EMBED Equation.3 1415 принимает значения 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415 (3.3)
Условия интерполяции (3.3) приводят к системе из (n+1) линейных уравнений с (n+1) неизвестными – коэффициентами многочлена:
13 EMBED Equation.3 1415 (3.4)
Решая эту с.л.у. относительно 13 EMBED Equation.3 1415 получим аналитическое выражение многочлена (3.2).
Система (3.4) всегда будет иметь единственное решение, поскольку ее определитель не будет равен нулю. Отсюда и вытекает существование и единственность решения системы (3.4) и, следовательно, многочлена (3.2).
Интерполяция стандартно производится многочленами, степень которых на единицу меньше числа узлов.
3. Интерполяционный многочлен Лагранжа
Пусть функция F(x) задана таблицей (3.1).
Построим многочлен Ln(x), степень которого не выше, чем n, и для которого выполнены условия интерполяции
13 EMBED Equation.3 1415 (3.5)
Будем искать Ln(x) в виде
13 EMBED Equation.3 1415 (3.6),
где 13 EMBED Equation.3 1415- многочлен степени n, причем
13 EMBED Equation.3 1415 (3.7).
Очевидно, что требования (3.7) с учётом (3.6) вполне обеспечивает выполнение условий (3.5). Многочлен 13 EMBED Equation.3 1415составим следующим образом:
13 EMBED Equation.3 1415 (3.8)
13 EMBED Equation.3 1415- коэффициент, значение которого найдем из первой части условия (3.7):
13 EMBED Equation.3 1415
Подставим 13 EMBED Equation.3 1415 в (3.8) и далее с учётом (3.6) получим:
13 EMBED Equation.3 1415 (3.9)
Это и есть интерполяционный многочлен Лагранжа.
По таблице исходной функции F формула (3.9) позволяет довольно просто составить «внешний вид» многочлена.
Пример: Построить интерполяционный многочлен для функции, заданной таблицей значений:
х
1
3
4
F(x)
12
4
6
Решение:
Из таблицы следует, что n=2 (на 1 меньше, чем узлов).
13 EMBED Equation.3 1415
По формуле (3.9) получаем:
13 EMBED Equation.3 1415
Таким образом, интерполяционный многочлен для заданной функции имеет вид 13 EMBED Equation.3 1415
Построим график13 EMBED Equation.3 1415 и точки в одной координатной плоскости.
Контрольные вопросы
В каких случаях может потребоваться аппроксимация функции?
Какими критериями пользуются для определения «близости» функции?
На чем основывается доказательство существования и единственности интерполяционного многочлена для таблично заданной функции?
В какой форме строится интерполяционный многочлен Лагранжа?
Постройте блок-схему алгоритма метода Лагранжа.
Задачи
Задание 1. По заданной таблице значений функции (таблица 1)
х
х0
х1
х2
х3
у
у0
у1
у2
у3
составить формулу интерполяционного многочлена Лагранжа. Построить его график и отметить на нем узловые точки.
Задание 2. Вычислить с помощью калькулятора одно значение заданной функции для промежуточного значения аргумента (таблица 2) с помощью интерполяционного многочлена Лагранжа и оценить погрешность интерполяции.
Таблица 1 Таблица 2
х0
х1
х2
х3
у0
у1
у2
у3
1
0
3
8
11
1
5
-4
-8
2
-3
-1
1
3
11
-1
6
-2
3
-4
0
2
5
4
8
-2
-9
Вариант
х
1
4.6
2
-2.5
3
-1.2
Лекция 11
«Интерполяционные формулы Ньютона»
План лекции
Интерполяционные формулы Ньютона. Конечные разности.
Первая интерполяционная формула Ньютона.
Вторая интерполяционная формула Ньютона.
1. Интерполяционные формулы Ньютона
Часто интерполирование ведется для функций, заданных таблично с равноотстоящими значениями аргумента. Шаг таблицы 13 EMBED Equation.3 1415 является постоянной величиной.
Для таких таблиц построение интерполяционных формул заметно упрощается.
Конечные разности
Пусть функция задана таблично с постоянным шагом:
таблица 3.2
x
x13 EMBED Equation.3 1415
x13 EMBED Equation.3 1415
x13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
F(x)
y13 EMBED Equation.3 1415
y13 EMBED Equation.3 1415
y13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Разности между значениями функций в соседних углах интерполяции называется конечными разностями первого порядка.
13 EMBED Equation.3 1415.
Из конечных разностей 1-го порядка образуются конечные разности второго порядка:
13 EMBED Equation.3 1415.
Продолжая этот процесс, можно по заданной таблице составить таблицу конечных разностей
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Конечные разности любого порядка могут быть представлены через значения функции.
Для разностей первого порядка это следует из определения:
13 EMBED Equation.3 1415.
Для разностей второго порядка имеем:
13 EMBED Equation.3 1415.
Аналогично для разностей третьего порядка:
13 EMBED Equation.3 1415
Используя метод математической индукции можно доказать:
13 EMBED Equation.3 1415.
2. Первая интерполяционная формула Ньютона
Пусть для функции заданной таблицей 3.2, составлена таблица конечных разностей.
Будем искать интерполяционный многочлен в виде
13 EMBED Equation.3 1415 (3.10)
13 EMBED Equation.3 1415-коэффициенты многочлена. Найдем их из условия совпадений значений исходной функции и многочлена в узлах.
Полагая x=x0, найдем y0=Pn(x0)=a0, следовательно, a0=y0 .
Далее, полагая 13 EMBED Equation.3 1415
13 EMBED Equation.3 1415.
При 13 EMBED Equation.3 1415имеем, 13 EMBED Equation.3 1415 т.е.
13 EMBED Equation.3 1415, откуда
13 EMBED Equation.3 1415
Аналогично, получим 13 EMBED Equation.3 1415.
Исходя из этих формул, можно записать 13 EMBED Equation.3 1415. (3.11)
Подставим (3.11) в выражение для многочлена (3.10), получим:
13 EMBED Equation.3 1415 . (3.12)
Часто эта формула записывается в ином виде.
Введем замену: 13 EMBED Equation.3 1415, или 13 EMBED Equation.3 1415.
Тогда13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415 и т.д.
13 EMBED Equation.3 1415.
Формула (3.12) примет вид:
13 EMBED Equation.3 1415. (3.13)
Формула (3.13) называется первой интерполяционной формулой Ньютона.
Замечание: Эта формула традиционно применяется для интерполирования в начале отрезка интерпретации. Потому её называют формулой для интерполирования вперед.
Пример: Построить интерполяционный многочлен Ньютона по следующим данным:
x
0,5
1
1,5
2
2,5
y
1,715
2,348
3,127
5,289
8,914
Решение: Построим таблицу конечных разностей
x
y
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
0,5
1,715
0,633
1
2,348
0,146
0,779
1,237
1,5
3,127
1,383
-1,157
2,162
0,080
2
5,289
1,463
3,625
2,5
8,914
По формуле (3.12) получим
13 EMBED Equation.3 141513 EMBED Equation.3 1415
По формуле (3.13) получим: 13 EMBED Equation.3 1415 и
13 EMBED Equation.3 1415
3. Вторая интерполяционная формула Ньютона
Когда значение аргумента находится ближе к концу отрезка интерполяции, применять первую интерполяционную формулу Ньютона становится невыгодно.
В этом случае применяется формула для интерполирования назад - вторая интерполяционная формула Ньютона, которая ищется в виде
13 EMBED Equation.3 1415 (3.14)
Коэффициенты 13 EMBED Equation.3 1415 находятся, как и для первой формулы
13 EMBED Equation.3 1415 (3.15)
Подставим формулу (3.15) в выражение (3.14) и перейдем к новой переменной: 13 EMBED Equation.3 1415, получим:
13 EMBED Equation.3 1415. (3.16)
Контрольные вопросы
Как находятся конечные разности различных порядков через значения функции в узловых точках?
Почему первую интерполяционную формулу Ньютона нецелесообразно применять для интерполирования в конце отрезка интерполяции, а вторую – в начале отрезка интерполяции?
Лекция 12
«Интерполяция сплайнами»
План лекции
Интерполяция сплайнами.
Пример построения кубического сплайна для функции y=f(x), заданной таблично.
1. Интерполяция сплайнами
При большом количестве узлов интерполяции сильно возрастает степень интерполяционных многочленов, что делает их неудобными для вычислений.
Высокой степени многочлена можно избежать, разбив отрезок интерполяции на несколько частей, с последующим построением на каждой части самостоятельного интерполяционного многочлена.
Однако такое интерполирование наталкивается на существенный недостаток: в точках стыка разных интерполяционных многочленов бывает разрывной их первая производная.
В этом случае удобно пользоваться особым видом кусочно-полиномиальной интерполяции - интерполяции сплайнами.
Суть этого подхода заключается в следующем:
Определение: Функция Sm (x) называется интерполяционным сплайном порядка m для функции f(x), заданной таблицей:
x
x13 EMBED Equation.3 1415
x13 EMBED Equation.3 1415
x13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
y
y13 EMBED Equation.3 1415
y13 EMBED Equation.3 1415
y13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
если:
на каждом отрезке [xi ; xi+1] (i=0,,n-1) S(x) является многочленом порядка m;
S(x) и её производная до (m-1)-го порядка включительно непрерывны на [x0 ; xn];
S(xi)=yi (i=0,,n) - непосредственно условие интерполяции.
Остановимся на построении наиболее популярных в практике аппроксимации функций кубических сплайнов.
По определению кубический сплайн S(x) можно представить в виде
13 EMBED Equation.3 1415 (3.17)
Где каждый из 13 EMBED Equation.3 1415 - многочлен третьей степени:
13 EMBED Equation.3 1415 . (3.18)
Коэффициенты 13 EMBED Equation.3 1415 найдем из условия: 13 EMBED Equation.3 1415, т.е.
13 EMBED Equation.3 1415 (3.19)
Условие непрерывности S(x) в каждом узле приводит к равенствам:
13 EMBED Equation.3 1415
В развернутом виде с учетом формулы (3.18) эти равенства примут вид:
13 EMBED Equation.3 1415 (3.20)
Введем обозначения: 13 EMBED Equation.3 1415
Понижая в равенстве (3.20) индекс на единицу (меняем i на i-1) и, учитывая (3.19), получим:
13 EMBED Equation.3 1415 (3.21)
Условие непрерывности первой производной кубического сплайна сводится к требованию 13 EMBED Equation.3 1415
Тогда дифференцируя формулу (3.18) и используя, введите обозначения, получим:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415) (3.22)
Из условия непрерывности второй производной: 13 EMBED Equation.3 1415получим:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415) (3.23)
Составим систему из равенств (3.21)-(3.23) и, решив её, найдем коэффициенты 13 EMBED Equation.3 1415.
Однако, для однозначной ее разрешимости добавим условия непрерывности на концах отрезка: 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 т.е.
13 EMBED Equation.3 1415 (3.24)
В результате получаем систему уравнений:
13 EMBED Equation.3 1415
Последовательно, исключая переменные получим
13 EMBED Equation.3 1415 (3.25)
(это уравнение содержит лишь неизвестные 13 EMBED Equation.3 1415).
13 EMBED Equation.3 1415 (3.26)
(это уравнение содержит лишь неизвестные 13 EMBED Equation.3 1415).
13 EMBED Equation.3 1415 (3.27)
(это уравнение содержит лишь неизвестные 13 EMBED Equation.3 1415).
Построив кубический сплайн, найдем оценку погрешности интерполяции:
13 EMBED Equation.3 1415,
где 13 EMBED Equation.3 1415 - промежуток интерполяции.
2. Пример построения кубического сплайна для функции y=f(x), заданной таблично
Пример: Построить кубический сплайн для функции y=f(x), заданной таблицей:
13 EMBED Equation.3 1415
-1
0
1
2
13 EMBED Equation.3 1415
1/2
1
2
4
с дополнительным условием: 13 EMBED Equation.3 1415. Найти с помощью S(x) значения функции при x=0,3. (Заметим, что в основу таблицы положена функция у =2x).
Решение:
Учитывая, что 13 EMBED Equation.3 1415 (т.к. вообще не используется в функциях) и 13 EMBED Equation.3 1415 (т.к. из условия (3.24):13 EMBED Equation.3 1415).
Шаг таблицы 13 EMBED Equation.3 1415.
из (3.25) получаем:
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
Из (3.26) имеем:
13 EMBED Equation.3 1415 ,
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415.
Из (3.27) имеем:
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415.
из формулы (3.18) получаем:
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415
Следовательно, сплайн S(x) построен:
13 EMBED Equation.3 1415
Найдем его значение при x=0,3:
Заметим, что 0,313 EMBED Equation.3 1415[0;1], поэтому используем многочлен 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415.
Отметим для сопоставления с той же точностью значение функции, положенной в основу данного примера:13 EMBED Equation.3 1415.
Интерполяция сплайнами сопряжена с немалым объемом вычислительной работы. Весьма необычна и форма окончательного результата, ибо сплайн имеет различные представления на различных частичных отрезках интерполяции. Это осложняет доступ к значениям сплайна в каждой конкретной точке, так как предполагает, прежде всего, поиск параметров, определяющих соответствующую форму сплайна. Эти трудности легко предотвратимы при использовании компьютера, так как упорядоченное хранение всех необходимых параметров организовать нетрудно, а выполнение однотипных процедур по вычислению параметров сплайна и его значений может быть обеспечено специальными процедурами.
Контрольные вопросы
Какой недостаток «кусочного» интерполирования с помощью многочленов Лагранжа и Ньютона устраняется при интерполировании сплайнами?
Дайте определение сплайна.
Какие трудности возникают при интерполировании сплайнами?
Задачи
Задание 1. По заданной таблице значений функции
х
х0
х1
х2
х3
у
у0
у1
у2
у3
вычислить коэффициенты и составить формулы кубического сплайна. Результат интерполирования проверить путем вычисления значений сплайна в узловых точках.
Построить график кубического сплайна и отобразить на нем узловые точки.
Вычислить с помощью калькулятора одно значение заданной функции для промежуточного значения аргумента с помощью построенного сплайна.
Таблица 1 Таблица 2
х0
х1
х2
х3
у0
у1
у2
у3
1
0
3
8
11
1
5
-4
-8
2
-3
-1
1
3
11
-1
6
-2
3
-4
0
2
5
4
8
-2
-9
Вариант
х
1
4.6
2
-2.5
3
-1.2
Практические занятия
Практическое занятие №6 «Составление интерполяционных формул Лагранжа и Ньютона: разработка алгоритма и программы для решения вычислительных задач, учитывая необходимую точность получаемого результата»
Практическое занятие №7 «Интерполирование сплайнами: разработка алгоритма и программы для решения вычислительных задач, учитывая необходимую точность получаемого результата»
Тема 2.4. Численное интегрирование
Лекция 13
«Формулы Ньютона-Котеса: метод прямоугольников»
План лекции
Постановка задачи численного интегрирования.
Квадратурные формулы Ньютона-Котеса.
Метод прямоугольников.
1. Подстановка задачи численного интеграла
При вычислении определенного интеграла
13 EMBED Equation.3 1415 ,
где f(x) - функция непрерывная на отрезке [a,b] используется формула Ньютона - Лейбница:
13 EMBED Equation.3 1415 (4.1)
Однако бывают случаи, когда первообразную F(x) нельзя найти, или не всегда удается довести вычисления до числового значения. Иногда подынтегральная функция может быть задана таблично или графиком, поэтому формула (4.1) не исчерпывает практических приемов вычисления интегралов.
На практике часто применяют различные методы приближенного (численного) интегрирования.
Определение: Формулы, используемые для приближенного вычисления интегралов, называют квадратурными формулами.
Простой прием построения квадратурных формул состоит в том, что подынтегральная функция f(x) заменяется на отрезке [a;b] интерполяционным многочленом Лагранжа Ln(x), и тогда:
13 EMBED Equation.3 1415 . (4.2)
Подобный подход удобен тем, что он приводит к алгоритмам, легко реализуемым на компьютере, и позволяющим получать результат с точностью, достаточной для широкого круга практических приложении.
2. Квадратурные формулы Ньютона – Котеса
Используя интерполяционные формулы Ньютона, и применяя замену
13 EMBED Equation.3 1415 или 13 EMBED Equation.3 1415,
получим следующий вид квадратурных формул Ньютона - Котеса
13 EMBED Equation.3 1415. (4.3)
дающих на одном участке интегрирования различные представления для различного числа n отрезков разбиения
13 EMBED Equation.3 1415 (4.4)
Числа 13 EMBED Equation.3 1415, называются коэффициентами Котеса.
Различают 3 вида квадратурных формул Ньютона - Котеса:
Формула прямоугольников.
Формула трапеции.
Формула Симпсона (параболы).
3. Метод прямоугольников
Для вычисления определенного интеграла 13 EMBED Equation.3 1415 отрезок [a;b] разбивают на n криволинейную трапецию, заменяют прямоугольником с основанием 13 EMBED Equation.3 1415, и высотой 13 EMBED Equation.3 1415 соответственно.
Данный подход к решению задачи дает площадь криволинейной трапеции, т.е. значение определенного интеграла с недостатком
13 EMBED Equation.3 1415. (4.5)
Формула (4.5) называется формулой прямоугольников с недостатком.
Аналогично можно получить формулу для вычисления определенного интеграла с избытком.
13 EMBED Equation.3 1415 (4.6)
Формула (4.6) называется формулой прямоугольников с избытком.
где значение
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415. (4.7)
Пример: Вычислить по формуле прямоугольников интеграл
13 EMBED Equation.3 1415 (n=5).
Решение:
Имеем a=0, 13 EMBED Equation.3 1415 , 13 EMBED Equation.3 1415.
Тогда 13 EMBED Equation.3 1415
Вычислим значение функции по формуле (4.7):
13 EMBED Equation.3 1415
Применяя формулу прямоугольника с недостатком (4.2) получим
13 EMBED Equation.3 1415
Вычислим данный интеграл по формуле Ньютона - Лейбница и сравним результаты:
13 EMBED Equation.3 1415
Относительная погрешность вычисления: 13 EMBED Equation.3 1415.
Контрольные вопросы
Почему формула Ньютона-Котеса может оказаться непригодной для реального вычисления определенного интеграла?
Как связаны задачи численного интегрирования и интерполирования?
Чем объясняется название формулы прямоугольников?
Задачи
Вычислить интеграл от заданной функции f(x) на отрезке [a;b] при делении отрезка на 10 равных частей по формуле прямоугольников.
№ задания
f(x)
a
b
1
13 EMBED Equation.3 1415
0
1
2
13 EMBED Equation.3 1415
0
1
3
13 EMBED Equation.3 1415
0
1
Лекция 14
«Формулы Ньютона-Котеса: метод трапеций»
План лекции
Метод трапеций.
1. Метод трапеций
Геометрический смысл этого метода практического вычисления определенного интеграла состоит в том, что нахождение площади криволинейной трапеции заменяется нахождением площади приблизительно равновеликой прямолинейной трапеции.
13 EMBED Equation.3 1415 (4.8)
Для повышения точности результата разобьём фигуру на n частей, а затем суммируем площади получившихся трапеций:
13 EMBED Equation.3 1415 (4.9)
где 13 EMBED Equation.3 1415.
Формула (4.9) называется формулой трапеций.
Пример: По формуле трапеции вычислить интеграл
13 EMBED Equation.3 1415 (n=5).
Решение: Имеем a=0, b=5, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Вычислим промежуточные значения функции в узлах:
13 EMBED Equation.3 1415
Тогда по формуле трапеций (4.9) имеем:
13 EMBED Equation.3 1415.
Контрольные вопросы
Чем объясняется название формулы трапеций?
Запишите форму трапеций.
Задачи
Вычислить интеграл от заданной функции f(x) на отрезке [a;b] при делении отрезка на 10 равных частей по формуле трапеций.
Сопоставьте результаты с ранее полученными.
№ задания
f(x)
a
b
1
13 EMBED Equation.3 1415
0
1
2
13 EMBED Equation.3 1415
0
1
3
13 EMBED Equation.3 1415
0
1
Лекция 15
«Формулы Ньютона-Котеса: метод парабол»
План лекции
Метод парабол.
1. Метод парабол
Замена подынтегральной функции f(x) параболой, проходящей через точки Mi(xi ; yi), (i=0,1,2) позволяет получать более точное значение определенного интеграла.
Если считать, что n - четное (n=2m), то получим:
13 EMBED Equation.3 1415 (4.10)
где 13 EMBED Equation.3 1415.
Формула (4.10) называется формулой парабол или формулой Симпсона.
Для оценки погрешности формулы Симпсона применяется формула
13 EMBED Equation.3 1415, (4.11)
Как следует из оценки, формула Симпсона, оказывается точной для многочленов до 3-ей степени включительно. Так как для этих случаев производная 4-го порядка равна 0.
Формула Симпсона обладает повышенной точностью по сравнению с формулой трапеций, это обозначает, что для достижения той же точности, что и в формуле трапеций, в ней можно брать меньшее число n - отрезков разбиения. Последнее обстоятельство весьма важно для вычислений. Поскольку основное время затрачивается на нахождение значений функции в узлах. Укажем простой практический прием, позволяющий прогнозировать требуемое число отрезков разбиения по заданной точности13 EMBED Equation.3 1415.
13 EMBED Equation.3 1415, (4.12)
Пример: Вычислить интеграл по формуле парабол
13 EMBED Equation.3 1415, (n=10).
Решение: Значения подынтегральной функции в узловых точках запишем в таблицу:
xi
13 EMBED Equation.3 1415
0
0
0,1
0,0019966
0,2
0,0079467
0,3
0,0531936
0,4
0,0623068
0,5
0,2397124
0,6
0,2032711
0,7
0,6313333
0,8
0,4591078
0,9
1,2689896
1
0,841478
Подставим найденные значения в формулу Симпсона, учитывая, что h=0,1:
13 EMBED Equation.3 1415
В данном случае легко вычислить «точное» значение этого интеграла, пользуясь формулой Ньютона - Лейбница
13 EMBED Equation.3 1415.
Как видим, результат, полученный с помощью приближенной формулы парабол, дает высокую точность.
Контрольные вопросы
В чем выражается преимущества формулы Симпсона перед формулой трапеций?
Каким образом при использовании формулы парабол можно рассчитать требуемое число отрезков разбиения для достижения заданной точности интегрирования 13 EMBED Equation.3 1415?
Задачи
Вычислить интеграл от заданной функции f(x) на отрезке [a;b] при делении отрезка на 10 равных частей по формуле парабол.
Сопоставьте результаты с ранее полученными.
№ задания
f(x)
a
b
1
13 EMBED Equation.3 1415
0
1
2
13 EMBED Equation.3 1415
0
1
3
13 EMBED Equation.3 1415
0
1
Лекция 16
«Формулы Гаусса»
План лекции
Квадратные формулы Гаусса.
1. Квадратные формулы Гаусса
Существует подход к построению квадратурных формул, в котором главную роль играет выбор узлов для интерполирования подынтегральной функции, называемый методом Гаусса.
При получении квадратных формул Гаусса в исходном интеграле выполняется замена переменной, переводящая интеграл по отрезку [a;b] в интеграл по отрезку [-1;1].
13 EMBED Equation.3 1415или 13 EMBED Equation.3 1415 (4.13)
Тогда
13 EMBED Equation.3 1415 (4.14)
Последний интеграл обозначим 13 EMBED Equation.3 1415и можно далее, развивать метод Гаусса применительно к нему.
Для разъяснения существа метода Гаусса будем использовать простейшую (линейную) интерполяцию подынтегральной функции:
Если в качестве узлов интерполяции взять концы отрезка [-1;1], то различие в площадях криволинейной трапеции, ограниченной сверху кривой 13 EMBED Equation.3 1415и «обычной» трапеции, ограниченной сверху прямой, проведённой через концы указанной кривой, фиксировано видом функции 13 EMBED Equation.3 1415.
Однако, если сделать узлы интерполяции «подвижными», то можно выбрать их таким образом, чтобы разность между площадями криволинейной и «обычной» трапеции была значительно меньше.
Более того, можно сделать эти площади равными 13 EMBED Equation.3 1415, т.е. аппроксимировать интеграл точно, но для этого необходимо определить точки 13 EMBED Equation.3 1415.
Сформулируем задачу следующим образом:
Выбрать значения 13 EMBED Equation.3 1415 так, чтобы площадь трапеции, ограниченной сверху прямой, проходящей через точки13 EMBED Equation.3 1415, была равна интегралу от любого многочлена некоторой (наивысшей возможной) степени.
Так как положение точек 13 EMBED Equation.3 1415 определяют четыре координаты, то это многочлен может определяться максимум четырьмя коэффициентами, т.е. является многочленом третьей степени.
13 EMBED Equation.3 1415 (4.15)
Легко установить, что уравнение прямой, проходящей через точки 13 EMBED Equation.3 1415 имеет вид: 13 EMBED Equation.3 1415, (4.16)
где 13 EMBED Equation.3 1415.
Будем выбирать 13 EMBED Equation.3 1415так, чтобы равенство
13 EMBED Equation.3 1415 (4.17)
имело место при любых 13 EMBED Equation.3 1415.
Вычисляя значения 13 EMBED Equation.3 1415, получим:
Если взять узлами линейной интерполяции числа13 EMBED Equation.3 1415 (4.18) ,то интеграл, вычисленный по формуле13 EMBED Equation.3 1415,точно совпадает с интегралом от любого многочлена третьей степени.
Вычислив интеграл по указанной формуле с учётом (4.18), получим
13 EMBED Equation.3 1415 (4.19)
Формула (4.19) и называется квадратурной формулой Гаусса.
С учетом формулы (4.14) формула Гаусса примет вид:
13 EMBED Equation.3 1415 (4.20)
Оценка погрешности вычисления интеграла по формуле (4.19) проводится по формуле:
13 EMBED Equation.3 141513 EMBED Equation.3 1415 (4.21)
Для повышения точности результата отрезок [a;b] разделим на n частей и применим формулу (4.20) на каждом из них.
Получим формулу для вычисления интеграла:
13 EMBED Equation.3 1415 (4.22)
Формула для оценки погрешности примет вид:
13 EMBED Equation.3 1415 (4.23)
Пример: Вычислить интеграл 13 EMBED Equation.3 1415 по формуле Гаусса при n = 10.
Решение: Имеем a = 0, b = 1, 13 EMBED Equation.3 1415.
Тогда 13 EMBED Equation.3 1415.
Составим таблицу значений, входящих в формулу (4.22)
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
0
0,02113249
0,078868
0,00000944
0,00049005
0,1
0,121132249
0,178868
0,00177304
0,00569215
0,2
0,22113249
0,278868
0,01072537
0,02140672
0,3
0,32113249
0,378868
0,03255086
0,05309115
0,4
0,42113249
0,478868
0,07250071
0,10566206
0,5
0,52113249
0,578868
0,13520907
0,18331848
0,6
0,62113249
0,678868
0,22452206
0,28938023
0,7
0,72113249
0,778868
0,34334373
0,42614496
0,8
0,82113249
0,878868
0,49350196
0,59476723
0,9
0,92113249
0,978868
0,67563779
0,795162236
1,0
13 EMBED Equation.3 1415
Подставляя найденное значение суммы значений функции yi , в формулу (4.22) получим:
13 EMBED Equation.3 1415.
Контрольные вопросы
На какой идее основывается построение квадратурных формул Гаусса?
Задачи
Вычислить интеграл от заданной функции f(x) на отрезке [a;b] при делении отрезка на 10 равных частей по формулам Гаусса.
Сопоставьте результаты с ранее полученными.
№ задания
f(x)
a
b
1
13 EMBED Equation.3 1415
0
1
2
13 EMBED Equation.3 1415
0
1
3
13 EMBED Equation.3 1415
0
1
Практические занятия
Практическое занятие №8 «Вычисление интегралов при помощи формул Ньютона-Котеса: разработка алгоритма и программы для решения вычислительных задач, учитывая необходимую точность получаемого результата»
Практическое занятие №9 «Вычисление интегралов при помощи формул Гаусса: разработка алгоритма и программы для решения вычислительных задач, учитывая необходимую точность получаемого результата»
Тема 2.5. Численное решение обыкновенных дифференциальных уравнений
Лекция 17
«Метод Эйлера»
План лекции
Постановка задачи.
Метод Эйлера решения дифференциальных уравнений
1. Численные методы решения дифференциальных уравнений.
Постановка задачи
Простейшим обыкновенным дифференциальным уравнением является уравнение первого порядка, разрешенное относительно производной:
y’=f(x,y) (5.1)
Эта задача известна, как задача Коши: найти решение уравнения (5.1) в виде функции y(x), удовлетворяющей начальному условию
y(x0) = y0. (5.2)
Геометрически это означает, что требуется найти интегральную кривую y=y(x), проходящую через заданную точку М0 (x0,y0), при выполнении равенства (5.1).
Существует несколько классов дифференциальных уравнений 1-го порядка, для которых решение может быть найдено аналитически. Но даже для таких уравнений решение не всегда удается довести до вида y=y(x). Многие же дифференциальные уравнения, к которым приводят математические модели реальных процессов, не могут быть решены аналитически. По этой причине разработаны многочисленные методы приближенного решения дифференциальных уравнений.
Эти методы подразделяются на 3 основные группы:
аналитические методы, применения которых дает приближенное решение дифференциальных уравнений в виде формулы;
графические методы, дающие приближенное решение в виде графика;
численные методы, когда искомая функция получается в виде таблицы.
2. Метод Эйлера
В основе метода ломанных Эйлера лежит идея графического построения решения дифференциального уравнения. Однако этот метод дает одновременно и способ нахождения искомой функции в численной (табличной) форме.
Пусть дано уравнение (5.1) с начальным условием (5.2), т.е. поставлена раздача Коши.
Вначале найдем простейшим способом приближенное значение решения в некоторой точке 13 EMBED Equation.3 1415, где h – достаточно малый шаг.
Заметим, что уравнение (5.1) совместно с начальным условием (5.2) задают направление касательной к искомой интегральной кривой в точке М13 EMBED Equation.3 1415(x13 EMBED Equation.3 1415,y13 EMBED Equation.3 1415). Двигаясь вдоль этой касательной, получим приближенное значение решения в точке х13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415 (5.3)
Аналогично, найдем приближенное значение решения в точке 13 EMBED Equation.3 1415, и т.д.
Продолжая эту идею, построим систему равностоящих точек 13 EMBED Equation.3 1415, i=0,..,n.
Получение таблицы значений искомой функции y(x) по методу Эйлера заключается в циклическом применении пары формул:
13 EMBED Equation.3 1415 (5.4)
Геометрическая иллюстрация метода Эйлера:
Рис 5.1 Построение ломаной Эйлера
Вместо кривой в реальности получается совокупность прямых – ломаная Эйлера.
Методы численного интегрирования дифференциальных уравнений, в которых решение получается от одного узла к другому, называются пошаговыми.
Метод Эйлера – простейший пошаговый метод.
Отметим, что оценка погрешности метода при таком элементарном рассмотрении невозможна даже на первом шаге. Кроме того, особенностью любого пошагового метода является то, что, начиная со второго шага, исходное значение y13 EMBED Equation.3 1415 в формуле (5.4) само является приближенным, т.е. погрешность на каждом шаге систематически возрастает.
Наиболее используемым методом оценки точности, как метода Эйлера, так и других пошаговых методов приближенного численного интегрирования обыкновенных дифференциальных уравнений является способ двойного прохождения заданного отрезка с шагом h и с шагом h/2. Совпадение соответствующих десятичных знаков в полученных двумя способами результатах дает основание считать их верными.
Пример: Решить методом Эйлера дифференциальное уравнение 13 EMBED Equation.3 1415c начальным условием y(0) = 1,3 на отрезке [0;1] применив h=0,2.
Решение: Имеем 13 EMBED Equation.3 1415.
Составим таблицу значений функции f(x,y) с шагом h и h/2.
x
yi (h=0.2)
yi (h=0.1)
0
1.3
1.3
0.1
1.33
0.2
1.35
1.38
0.3
1.46
0.4
1.52
1.56
0.5
1.68
0.6
1.77
1.82
0.7
1.98
0.8
2.09
2.15
0.9
2.33
1
2.47
2.53
При составлении таблицы проводились следующие вычисления:
Если h=0,2:
х0=0, у0=1,3 из начального условия;
х1=0,1,
13 EMBED Equation.3 1415
х2=0,2,
13 EMBED Equation.3 1415
И т.д.
Аналогичные вычисления проводились и для h=0,1.
Таким образом, приближенное решение уравнения получаем в виде таблицы. Построим ломаную Эйлера для h=0,2 и h=0,1 в одной системе координат.
Контрольные вопросы
Что является решением дифференциального уравнения?
На какие группы подразделяются приближенные методы решения дифференциальных уравнений?
В какой форме получается приближенное решение дифференциального уравнения по методу Эйлера?
Задачи
Решить задачу Коши для дифференциального уравнения y’=f(x,y) на отрезке [a;b] при заданном начальном условии y(a)=y0 и шаге интегрирования h.
Найти точное решение задачи Коши.
Методом Эйлера с применением «ручных» вычислений с шагом 2рррр
h, а также с помощью программы для компьютера с шагом h.
Свести результаты вычислений в одну таблицу и сопоставить точность полученных значений функции.
Пользуясь таблицей, сделать ручную прикидку графика интегральной кривой на бумаге.
уравнение
a
b
y0
h
1
13 EMBED Equation.3 1415
2.3
4
1
0.2
2
13 EMBED Equation.3 1415
1,5
3,8
1
0.2
3
13 EMBED Equation.3 1415
3
1
1
0,2
Лекция 18
«Метод Рунге-Кутта»
План лекции
Метод Рунге-Кутта решения дифференциальных уравнений.
1. Метод Рунге-Кутта
Если к методу Эйлера подойти другим путем, не используя геометрических построений, то необходимо рассматривать производные функции f(x,y) и раскладывать эту функцию в степенной ряд. Но нахождение производных не является стандартной задачей, применяемой при решении математических задач систем программирования.
Альтернативный путь открывает метод Рунге-Кутта, названный по имени его создателей.
Основная идея метода Рунге-Кутта такова: вместо использования в формулах частных производных функции f(x,y) использовать лишь саму эту функцию, но на каждом шаге вычислять ее значение в нескольких точках.
На практике соблюдается некоторый компромисс между высоким порядком формул и их громоздкостью с одной стороны, и объемом вычислений по ним для достижения заданной точности, с другой. Запишем самую распространяемую формулу Рунге-Кутта четвертого порядка:13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, (5.5)
13 EMBED Equation.3 1415 (5.6)
Общий недостаток методов Рунге-Кутта – отсутствие простых способов оценки погрешности метода. Погрешность на одном шаге оценить сравнительно не трудно, гораздо труднее оценить накопление погрешностей на протяжении многих шагов. Широко используемый на практике для этих методов способ контроля точности – двойной счет: вычисляем решение дифференциального уравнение с шагом h и h/2 , а потом сравниваем полученные результаты.
Пример: Решить дифференциальное уравнение 13 EMBED Equation.3 1415 на отрезке 13 EMBED Equation.3 1415 с начальным условием у(0)=1 и шагом h=0.05.
Решение: Сначала решим это уравнение аналитически:
13 EMBED Equation.3 1415- уравнение с разделяющимися переменными.
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415
Применим начальное условие 13 EMBED Equation.3 1415, получим:
13 EMBED Equation.3 1415
Таким образом, частное решение данного уравнения, удовлетворяющее заданному начальному условию:
13 EMBED Equation.3 1415.
Пользуясь этой формулой, можно получить таблицу «точного» решение уравнения.
Найдем приближенное решение дифференциальное уравнение по методу Рунге-Кутта. Проведем последовательные вычисления по формулам (5.5), (5.6):
Имеем: f(x,y)=y(1-x), 13 EMBED Equation.3 1415=0, 13 EMBED Equation.3 1415=1, h=0.05. Тогда
13 EMBED Equation.3 1415
Подставим найденные значения в формулу (5.5):
13 EMBED Equation.3 1415
Поскольку вычисления достаточно громоздки и трудоемки, то численные решения заданного уравнения можно найти с помощью программы на компьютере.
Для сравнения результатов построим таблицу, в которой укажем численные решения, полученные по методу Эйлера, методу Рунге-Кутта и «точное решение».
Х
У
метод Эйлера
метод Рунге-Кутта
«точное решение»
0,00
0,05
0,10
0,15
0,20
0,25
0,30
0,35
0,40
0,45
0,50
1
1,05
1,0999
1,1494
1,1982
1,2462
1,2929
1,3381
1,3816
1,4231
1,4622
1
1,0499
1,0997
1,1488
1,1972
1,2445
1,2905
1,3348
1,3771
1,4173
1,4550
1
1,0499
1,0997
1,1488
1,1972
1,2445
1,2905
1,3348
1,3771
1,4173
1,4550
Из таблицы видно, что результаты, получения по методу Рунге-Кутта практически совпадают с «точным» решением уравнения, в отличие от соответствующих значений, полученных по методу Эйлера.
Контрольные вопросы
В чем основная идея метода Рунге-Кутта?
В чем отличие одношаговых методов Эйлера и Рунге-Кутта?
Практические занятия
Практическое занятие №10 «Нахождение решений обыкновенных дифференциальных уравнений с использованием методов Эйлера: разработка алгоритма и программы для решения вычислительных задач, учитывая необходимую точность получаемого результата»
КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Вопросы к экзамену
ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ВОПРОСОВ ДЛЯ ПОДГОТОВКИ К СДАЧЕ ЭКЗАМЕНА ПО ДИСЦИПЛИНЕ «ЧИСЛЕННЫЕ МЕТОДЫ»
Раздел 1. Действия над приближенными числами
Приближенные числа. Верные цифры числа. Погрешности приближенных значений чисел.
Вычисление погрешностей арифметических действий.
Оценка погрешностей значений функций.
Способы приближенных вычислений по заданной формуле. Вычисление по правилам подсчета цифр.
Способы приближенных вычислений по заданной формуле. Вычисление со строгим учетом предельных абсолютных погрешностей.
Способы приближенных вычислений по заданной формуле. Вычисление по методу границ.
Раздел 2. Численные методы решения основных математических задач
Тема 2.1. Решение линейных и трансцендентных уравнений с помощью ЭВМ
Приближенные решения алгебраических уравнений. Метод половинного деления.
Приближенные решения алгебраических уравнений. Метод касательных.
Приближенные решения алгебраических уравнений. Метод хорд.
Тема 2.2. Решение систем уравнений с помощью ЭВМ
Решение систем линейных алгебраических уравнений. Метод Гаусса.
Вычисление определителей методом Гаусса.
Нахождение обратной матрицы методом Гаусса.
Решение систем линейных алгебраических уравнений. Метод простой итерации.
Решение систем линейных алгебраических уравнений. Метод Зейделя.
Тема 2.3. Интерполирование и экстраполирование функций
Интерполирование функций. Аппроксимация функций.
Интерполирование функций. Интерполяционный многочлен Лагранжа.
Интерполирование функций. Конечные разности.
Интерполирование функций. Первая интерполяционная формула Ньютона.
Интерполирование функций. Вторая интерполяционная формула Ньютона.
Интерполирование функций. Интерполяция сплайнами.
Тема 2.4. Численное интегрирование
Численное интегрирование. Постановка задачи численного интегрирования. Квадратурные формулы Ньютона-Котеса.
Численное интегрирование. Квадратурные формулы Ньютона-Котеса. Формула прямоугольников.
Численное интегрирование. Квадратурные формулы Ньютона-Котеса. Формула трапеций.
Численное интегрирование. Квадратурные формулы Ньютона-Котеса. Формула Симпсона.
Численное интегрирование. Квадратурные формулы Гаусса.
Тема 2.5. Численное решение обыкновенных дифференциальных уравнений
Численные методы решения дифференциальных уравнений. Постановка задачи. Метод Эйлера.
Численные методы решения дифференциальных уравнений. Постановка задачи. Метод Рунге-Кутта.
ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
Основные источники
Колдаев В.Д. Численные методы и программирование: учебное пособие для СПО / В.Д. Колдаев; под ред. проф. Л.Г. Гагариной. – М.: ИД «ФОРУМ»: ИНФРА-М, 2010.
Дополнительные источники
Самарский А.А. Задачи и упражнения по численным методам; Москва,2000.
Лабораторный практикум по курсу «Основы вычислительной математики»; Москва,2009.
Н. С. Бахвалов, А. В. Лапин, Е. В. Чижонков Численные методы в задачах и упражнениях; БИНОМ. Лаборатория знаний,2011.
Пакет прикладных программ по курсу численные методы OC Windows, XP – сервисная программа. MS Office, XP – сервисная программаю
Периодические издания
Научный журнал «Вычислительные методы и программирование. Новые вычислительные технологии»
Exponenta Pro. Математика в приложениях
Математические заметки
Интернет-ресурсы:
Единое информационно-образовательное пространство колледжа NetSchool. Форма доступа: http://sgtek.ru
Информационно-справочная система «В помощь студентам». Форма доступа: http://window.edu.ru
Информационно-справочная система. Форма доступа: [ Cкачайте файл, чтобы посмотреть ссылку ].
Информационно-справочная система. Форма доступа: [ Cкачайте файл, чтобы посмотреть ссылку ]
13PAGE 15
13 PAGE \* MERGEFORMAT 147915
Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Nativeл 3 2л 4 3Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native5Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Nativekл13 1л 14 1Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Nativeл 15 1Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Nativeл 17 2Equation NativeEquation NativeEquation NativeEquation NativeEquation Native