Лекции по дисциплине "Численные методы"

Министерство образования Оренбургской области

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

 «Оренбургский колледж экономики и информатики»

КОНСПЕКТ ЛЕКЦИЙ

учебной дисциплины

«Численные методы»

Оренбург 2015

Автор:

преподаватель высшей

квалификационной категории    

ГАПОУ ОКЭИ                                           __________ С.В.Зеленина

Содержание

1. Пояснительная записка________________________________________
2. Конспекты лекций:____________________________________________

 Введение (2 часа)

Раздел 1. Приближённые числа и действия над ними (8 часов)________

Тема 1.1. Точные и приближённые числа. Округление чисел (2 часа)_____

Тема 1.2. Абсолютная и относительная погрешность округления (2часа)__

Тема 1.3. Арифметические действия над приближёнными

числами (4 часа)_________________________________________________

Раздел 2. Численные методы (44 часа)_______________________________

Тема 2.1. Приближённое решение алгебраических и трансцендентных уравнений (12 часов)_____________________________________________

Тема 2.2. Решение систем линейных уравнений (8 часов)_______________

Тема 2.3. Интерполирование и экстраполирование (8 часов)____________

Тема 2.4. Численное интегрирование (8 часов)________________________

Тема.2.5.Численное решение обыкновенных дифференциальных уравнений (10 часов)_____________________________________________

Тема.2.6.Численное решение задач оптимизации (6 часов)____________

1. Пояснительная записка

Учебная дисциплина «Численные методы» рассчитана на студентов, освоивших курсы учебных дисциплин «Элементы высшей математики» и «Основы алгоритмизации и программирования». Программа дисциплины «Численные методы» предусматривает изучение методов решения  математических задач- приближённые вычисления, решение линейных и трансцендентных уравнений, решение систем уравнений, численное интегрирование, решение дифференциальных уравнений, интерполирование и экстраполирование. Данная дисциплина является важной в подготовке высококвалифицированных специалистов, так как численные методы являются основой программирования при решении математических задач. Материал, пре­дусмотренный программой, обладает особым качеством и возможностями для развития точного и математического мышления.

Программа курса  «Численные методы» рассчитана на 52 часа лекционных занятий, поэтому в методической разработке представлены конспекты лекций по 9 темам,  структура лекций соответствует календарно-тематическому плану и  рабочей программе по данной дисциплине.  Занятия по изучению теоретического материала проводятся в форме лекции, используя различные  методы обучения: объяснительно-иллюстративный, репродуктивный, проблемный, частично-поисковый, метод проб и ошибок. Контроль знаний  студентов по темам дисциплины проводится в виде самостоятельной работы по карточкам, словесного диктанта, контрольной работы, тестов и выполнения лабораторных работ на базе ПК.

В результате изучения дисциплины  студент должен:

Иметь представление:

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

Знать:

-   оценку точности вычислений, т.е. действия с приближёнными числами;

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

           Уметь:

-применять полученные знания при решении практических задач.

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

Лекционные материалы соответствуют дидактическим и воспитательным целям:

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

- в процессе лекции обеспечивается творческая работа учащихся совместно с преподавателем;

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

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

2. Конспекты лекций

Тип лекции: вводная

План:

1. Схема вычислительного эксперимента

2. Требования к вычислительным методам

3. Учет погрешностей приближенных вычислений

4.      Вопрос для самостоятельного изучения студентами:

-применение численных методов в программировании

- подготовка реферата по теме «История возникновения приближённых чисел»

1. Схема вычислительного эксперимента

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

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

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

Формулируются основные законы, управляющие данным объектом исследования (I)

 и строится соответствующая математическая модель   (II),

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

Рисунок 1 - Этапы построения и анализа с помощью ЭВМ математической модели объекта

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

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

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

Именно на этом этапе требуется привлечение ЭВМ и, как следствие, развитие численных методов (см. III на рис. 1).

Под численным методом здесь понимается такая интерпретация математической модели («дискретная модель»), которая доступна для реализации на ЭВМ.

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

Результатом реализации численного метода на ЭВМ является число или таблица чисел.

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

Чтобы реализовать численный метод, необходимо составить программу для ЭВМ (см. IV на рис. 1) или воспользоваться готовой программой. После отладки программы наступает этап проведения вычислений и анализа результатов (V). Полученные результаты изучаются с точки зрения их соответствия исследуемому явлению и, при необходимости, вносятся исправления в численный метод и уточняется математическая модель.

Такова в общих чертах схема вычислительного эксперимента. Его основу составляет триада: модель — метод (алгоритм) — программа.

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

Можно указать такие крупные области применения вычислительного эксперимента, как

энергетика,

 аэрокосмическая техника,

обработка данных натурного эксперимента,

совершенствование технологических процессов.

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

2. Требования к вычислительным методам.

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

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

К первой группе относятся такие требования, как

сходимость численного метода,

выполнение дискретных аналогов законов сохранения,

качественно правильное поведение решения дискретной задачи.

Поясним эти требования.

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

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

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

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

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

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

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

3 Учет погрешностей приближенных вычислений

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

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

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

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

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

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

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

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

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

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

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

Пусть  и  – два «близких числа»;  – точное,  – приближенное.

Величина  называется абсолютной погрешностью приближенного числа, а , но чаще  - относительной погрешностью.

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

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

Технический подход связан с именем известного русского кораблестроителя, математика и механика А.Н. Крылова.

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

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

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

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

2 При умножении и делении в результате нужно сохранять столько значащих цифр, сколько их имеет приближенное данное с наименьшим числом значащих цифр;

3 Результаты промежуточных данных должны иметь 1-2 запасных знаков, затем их отбрасывают.

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

Примеры:

1 Пусть , . В числе  верны в широком смысле цифры 2, 9, 1.

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

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

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

Пример ,  ,  

Перечень источников:

1. Вержбицкий В.М. Основы численных методов: учебник для вузов. М.: Высшая школа, 2002. - 302 с.

2. Лапчик М.П., Рагулина М.И.. Численные методы: учебное пособие для студентов вузов/.-М.: Издательский центр «Академия», 2004.- 362 с.

Раздел 1. Приближенные числа и действия над ними(10часов)

Тема 1.1. Точные и приближенные числа. Округление чисел (2часа)

Тип лекции: текущая

План:

1. Точные и приближенные числа

2. Округление чисел.

3. Упражнения

4. Вопрос для самостоятельного изучения:

-правила округления приближённых чисел

-подготовка реферата по теме: «История возникновения приближённых чисел».

1. Точные и приближенные числа

При решении задач очень часто ставится условие: вычислить результат с точностью до одной десятой, одной сотой и т.д.

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

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

Замечание. Нули в конце числа - всегда значащие цифры (в противном случае их не пишут)

Пример 1. числа 0,001604 - 4 значащих цифры; 30,500 - 5 значащих цифр.

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

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

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

Опр. Приближенное число

a=α₁×10^m+ α₂×10^m-1+… α_n×10^m-n+1+…

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

∆a≤0,5×10 ^m-n+1

Если это неравенство не выполняется, то цифру α_n называют сомнительной. Если цифра α_n - верная, то и все предшествующие её цифры тоже верные.

Опр. Приближенное число

a=α₁×10^m+ α₂×10^m-1+… α_n×10^m-n+1+…

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

∆a≤1×10 ^m-n+1

Пример:

Сколько верных значащих цифр содержит приближенное число а=85,267±0,0084 в узком и широком смысле.

а) а=0,0084,   а=8×10¹+5×10⁰+2×10^-1+6×10^-2+7×10^-3

«7»    0,0084>0,5-10^-3, 0,0084>0,0005 => цифра «7» сомнительная

«6»    0,0084>0,5-10^-2, 0,0084>0,005 => цифра «6» сомнительная

«2»    0,00840<5-10^-1 , 0,0084<0,05 => цифра «2» верная в узком смысле

Ответ: цифры 8,5,2 - верные в узком смысле

б)   «7»   0,0084> 1×10^-3,    0,0084>0,001 => цифра «7» сомнительная

       «6»   0,0084<1×10^-2,  0,0084<0,01 => цифра «6» верная в широком смысле

Ответ: цифры 8,5,2,6 - верные в широком смысле.

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

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

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

3.     Если первая слева из отброшенных цифр равна 5 и за ней не следует отличных от нуля цифр, то последняя оставшаяся цифра усиливается, если она нечетная, и остается без изменения, если она четная (правило четной цифры).

Пример: округляя число 5,785 до сотых получаем 5,78. усиление не делаем т.к. последняя сохраняемая цифра «8» - четная. Число 5,775 округляем до второго десятичного знака, имеем 5,78. последняя сохраняемая цифра «7» увеличивается на единицу, т.к. «7» - нечетная.

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

Пример:округляя число А=26,837 до трёх значащих цифр, получаем а=26,8, откуда ∆а=|А-а|=|26,837-26,8|=0,037. 0,037<0,5×0,1      0,037<0,05

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

∆а₂=∆а₁+ ∆_окр

1.                 Округлить соответственно до 2, 3, 4 знаков после запятой следующие числа: 3,009982; 24,00551; 21,161728.

2.                 У приближенных чисел 0,310; 3,495; 24,3790 все цифры верны в узком смысле. Округлить заданные числа до сотых и определить в округленных значениях количество цифр, верных в строгом смысле.

2.Округление чисел

При решении задач очень часто ставится условие: вычислить результат с точностью до одной десятой, одной сотой и т.д.

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

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

Замечание. Нули в конце числа - всегда значащие цифры (в противном случае их не пишут)

Пример 1. числа 0,001604 - 4 значащих цифры; 30,500 - 5 значащих цифр.

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

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

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

Опр. Приближенное число

a=α₁×10^m+ α₂×10^m-1+… α_n×10^m-n+1+…

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

∆a≤0,5×10 ^m-n+1

Если это неравенство не выполняется, то цифру α_n называют сомнительной. Если цифра α_n - верная, то и все предшествующие её цифры тоже верные.

Опр. Приближенное число

a=α₁×10^m+ α₂×10^m-1+… α_n×10^m-n+1+…

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

∆a≤1×10 ^m-n+1

Пример:

Сколько верных значащих цифр содержит приближенное число а=85,267±0,0084 в узком и широком смысле.

а) а=0,0084,   а=8×10¹+5×10⁰+2×10^-1+6×10^-2+7×10^-3

«7»    0,0084>0,5-10^-3, 0,0084>0,0005 => цифра «7» сомнительная

«6»    0,0084>0,5-10^-2, 0,0084>0,005 => цифра «6» сомнительная

«2»    0,00840<5-10^-1 , 0,0084<0,05 => цифра «2» верная в узком смысле

Ответ: цифры 8,5,2 - верные в узком смысле

б)   «7»   0,0084> 1×10^-3,    0,0084>0,001 => цифра «7» сомнительная

       «6»   0,0084<1×10^-2,  0,0084<0,01 => цифра «6» верная в широком смысле

Ответ: цифры 8,5,2,6 - верные в широком смысле.

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

Правила округления

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

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

6.         Если первая слева из отброшенных цифр равна 5 и за ней не следует отличных от нуля цифр, то последняя оставшаяся цифра усиливается, если она нечетная, и остается без изменения, если она четная (правило четной цифры).

Пример: округляя число 5,785 до сотых получаем 5,78. усиление не делаем т.к. последняя сохраняемая цифра «8» - четная. Число 5,775 округляем до второго десятичного знака, имеем 5,78. последняя сохраняемая цифра «7» увеличивается на единицу, т.к. «7» - нечетная.

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

Пример: округляя число А=26,837 до трёх значащих цифр, получаем а=26,8, откуда ∆а=|А-а|=|26,837-26,8|=0,037. 0,037<0,5×0,1    0,037<0,05

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

∆а₂=∆а₁+ ∆_окр

3. Упражнения:

1. Округлить соответственно до 2, 3, 4 знаков после запятой следующие числа: 3,009982; 24,00551; 21,161728.

2. У приближенных чисел 0,310; 3,495; 24,3790 все цифры верны в узком смысле. Округлить заданные числа до сотых и определить в округленных значениях количество цифр, верных в строгом смысле.

3. Округлить соответственно до 2, 3, 4 знаков после запятой следующие числа: 3,009982; 24,00551; 21,161728.

4. У приближенных чисел 0,310; 3,495; 24,3790 все цифры верны в узком смысле. Округлить заданные числа до сотых и определить в округленных значениях количество цифр, верных в строгом смысле.

5.            Округлить соответственно до 2, 3, 4 знаков после запятой следующие числа: 3,009982; 24,00551; 21,161728.

6.            У приближенных чисел 0,310; 3,495; 24,3790 все цифры верны в узком смысле. Округлить заданные числа до сотых и определить в округленных значениях количество цифр, верных в строгом смысле.

Тема 1.2. Абсолютная и относительная погрешность вычислений (2 часа)

Тип лекции: текущая

План:

1. Абсолютная и относительная погрешность вычислений

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

3. Упражнения

4. Вопрос для самостоятельного изучения:

-связь между абсолютной и относительной погрешностью

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

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

∆х=|а-х|, где а - точное значение, х - приближенное значение.

Опр. Относительной погрешностью δ приближенного значения х числа а называется отношение абсолютной погрешности этого приближения к числу х.

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

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

Чем меньше относительная погрешность, тем выше качество измерений или вычислений. Относительная погрешность позволяет сравнивать качество измерений величин разной размерности.

Пример: в результате измерений получили, что длина карандаша равна 16 см., а длина комнаты равна 730 см. Что можно сказать о качестве этих двух измерений?

Пусть границей абсолютной погрешности равна ±0,5см.Найдем относительную погрешность этих измерений:

≈3,12 % (при измерении карандаша)

≈0,0007≈0,07% (при измерении карандаша)

Качество измерения длины комнаты значительно выше, чем качество измерения длины карандаша.

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

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

∆a ≤ 0,5×10^m-n+1

разделив обе части неравенства на |а|, получим

,

а так как |a| = |α₁×10^m+ α₂×10^m-1+…+ α_n×10^m-1+1_…|

получаем

≤≤=

Если цифра α_n приближенного числа а верная, то за относительную погрешность можно принять

δ_a= (в узком смысле), δ_a=(в широком смысле).

где α₁ -первая значащая цифра числа, n-количество верных значащих цифр.

Пример:

1.   Какова предельная относительная погрешность приближенного числа
а=4,176, если оно имеет только верные цифры в узком смысле?

В приближенном числе 4 верных цифры, то предельную относительную погрешность вычисляют по формуле

δ_a===0,000125=0,0125%

2.         Какова предельная относительная погрешность числа а=14,278. если
оно имеет только верные цифры в широком смысле?

δ_a===0,0001=0,01%

3. Упражнения

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

а) 1,1426  б)0,01015  в) 921,55

2. Определить абсолютную погрешность следующих приближенных
чисел по их относительной погрешности:

а) х=2,52;                δ=0,7%;

б)х=0,986;               δ=10%;

в)х=46,72;               δ =1%;

г) х=199,1;              δ =0,01

д) х=0,86341; δ=0,0004

Тема 1.3. Арифметические действия над приближенными числами (6 часов)

Тип лекции: текущая

План:

1. Сумма приближенных чисел.

2. Разность приближенных чисел.

3. Погрешность произведения

4. Погрешность частного

5. Правила подсчёта цифр

6. Упражнения

7. Вопрос для самостоятельного изучения:

-Формулы для границ абсолютной и относительной погрешностей некоторых функций.

1. Сумма приближенных чисел

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

Пусть A=X₁+X₂+X₃+.. .+Х_n - сумма точных чисел; а=х₁+х₂+х₃+.. .+х_n - сумма приближенных значений этих чисел. Абсолютные погрешности соответственно равны Δх₁ Δх₂, Δх₃, ..., Δх_n . Вычитая из точного значения суммы приближенное её значение, имеем

А-а=(Х₁-х₁)+(Х₂-х₂)+(Х₃-х₃)+.. .+(Х_n+х_n)

Переходя к модулям, получаем

|А-а|≤| Х₁-х₁|+|Х₂-х₂|+| Х₃-х₃|+...| Х_n+х_n|

Следовательно, Δa<Δx₁+Δx₂+ Δx₃+...+ Δх_n,

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

При сложении чисел различной абсолютной точности обычно поступают следующим образом:

1)    выделяют число (или числа) наименьшей абсолютной точности (т.е. число, имеющее наибольшую абсолютную погрешность);

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

3)    произвести сложение, учитывая все сохраненные знаки;

4)    полученный результат округлить на один знак.

Пример 1: сложить несколько приближенных чисел

а=0,1732+17,45+0,000333+204,4+7,25+144,2+0,0112+0,634+0,0771

В каждом из приведенных чисел верны все значащие цифры (в широком смысле)

Решение:

1) числа с наименьшей точностью: 204,4 и 144,2 - верны с точностью до 0,1.

		0,	1	7
	1	7,	4	5
		0,	0	0
2	0	4,	4
		7,	2	5
1	4	4,	2
		0,	0	1
		0,	6	3
		0,	0	8
3	7	4,	1	99

2) остальные числа округляем,

0,1732≈0,17

17,45≈17,45

000333≈0,00

7,25≈7,25

0,0112≈0,01

0,0771≈0,08

3) складываем полученные числа с точностью до 0,01             2 j

4)374,19≈374,2

Оценим точность результата

Абсолютная погрешность=исходная погрешность+погрешность округления

1) сумма предельных погрешностей исходных данных

Δ₁=0,0001+0,01+0,000001+0,1+0,001+0,0001+0,001+0,0001=0,2213<0,222

0,05-2+0,005-7=0,135≈0,14 (цифры 2 и 7 - количество складываемых чисел)

2)  погрешность округления равна 0,01

3)  абсолютная величина суммы ошибок округления слагаемых

Δ₂=|0,0032+0,000333+0,0012+0,004-0,0029|=0,0058332 заключительной погрешности округления

Δа= 0,222+0,006+0,001=0,238<0,3<0,006

Ответ: а=374,2±0,3

Так, как абсолютная погрешность суммы вычисляется по формуле   Δa=Δx₁+Δx₂+ Δх₃+...+ Δx_n, а относительная δ_а=Δа-|а|, то

δ _min≤δ_а≤ δ _max                                         

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

Пример 2: Оценить относительную погрешность суммы чисел в примере 1 и сравнить её с относительными погрешностями слагаемых.

δ_а = = 0,0006 = 0,06%

Относительные погрешности слагаемых:

δ_а1 = ≈ 0,03 = 3%                            δ_а6 = ≈ 0,0003 = 0,03%

δ_а2 = ≈ 0,0003 = 0,03%                            δ_а7 = = 0,05 = 50%

δ_а4 = ≈ 0,0003 = 0,03%                           δ_а8 = ≈ 0,008 = 0,8%

δ_а5 = ≈ 0,0007 = 0,07%                             δ_а9 = ≈ 0,07 = 7%

Следовательно, δ_min = 0,03%, δ_тах = 50%, δ_а = 0,06% , тогда относительная погрешность суммы заключена между наименьшей и наибольшей относительными погрешностями слагаемых.

2. Разность приближенных чисел

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

δ_а = =

Пример 3: пусть х=5,125, у=5,135 тогда Δх=0,5×10^-3, Δу=0,5×10^-3

δ_а = ==0,1=10%

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

Пример 4: найти разность а= и оценить относительную погрешность результата.

а₁ = =2,504; ∆а₁=0,5×10^-3 =0,0005

а₂ =  = 2,502 _; ∆а₂ = 0,5 × 10^-3 = 0,0005

Тогда

а = 2,504 - 2,502 = 0,002 = 0,2 × 10^-2;

∆а = 0,0005 + 0,0005 = 0,001 = 0,1×10^-2

δ_а = =0,5=50%

Однако, изменив вычислительную схему, можно получить:

а====

=≈0,2×10^-2

δ_а = ==50,2×10^-3=0,02%

Таким, образом получили лучший результат относительной погрешности.

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

3. Погрешность произведения.

Рассмотрим два числа: а=х+∆х; в=у+∆у

перемножим, левые и правые части соотношений, получим:

ав=(х+∆х)(у+∆у)=ху+х∆у+∆ху+∆х∆у

переходя к абсолютным величинам правых и левых частей, находим

|ав-ху|=|х∆у+∆ху+∆х∆у|, по свойству модулей (модуль суммы меньше либо равен сумме модулей) получаем |ав-ху|≤|х∆у|+|∆ху|+|∆х∆у|.

Разделим левую и правую части неравенства на |ху|, тогда получаем

- относительная погрешность числа а,

- относительная погрешность числа в,

 - относительная погрешность произведения отбрасываем. В силу его малости. Тогда получаем  δ_аб ≤ δ_а+δ_b

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

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

Пусть U=k-a, где к- точный сомножитель (к≠0)

а=х+∆х,     a-k=kx+k∆x  , ak-kx=k∆x

|kа- kх| ≤ |k × ∆х| - раскрываем по свойству модулей,

|k|| а - х| ≤| k|×|∆х| разделим на |∆х|, получаем

,

а относительная погрешность в результате равна δ_a≤δ_х. Тогда абсолютная погрешность, будет равна

∆а=|a|×δ_a=|k×x|×||=|k|×∆x

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

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

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

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

Пример. Найти произведение приближенных чисел x₁=12,4 и х₂=65,54 и числоверных знаков, если все написанные цифры сомножителей верны в узком смысле.

Решение: так, как данные цифры имеют разное количество цифр после запятой, то эти цифры оставляем без изменения.

Находим произведение этих чисел: а=12,4×65,54=812,696; сохранить нужно три значащих цифры (по правилу), следовательно, получаем, а=813.

Подсчитаем погрешность:

δ_ab=δ_x1+δ_x2== 0,0040322 + 0,0000762= 0,0041094 ≈ 0,0041

Тогда Δa = |а|-δ_a=0,0041-813≈3

Ответ: а=813±3

4. Погрешность частного

Пусть имеем два числа а=х+Δх и в=у+Δу. Вычислим абсолютную погрешность частного:

Разделим обе части равенства на , получаем

Так, как Δу малая величина по сравнению с у, то выражение ,

тогда , следовательно - относительная погрешность частного не превышает суммы относительных погрешностей делимого и делителя.

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

Пример: вычислить частное а= приближенных чисел х=5,735 и у=1,23, все цифры верны в узком смысле. Определить относительную и абсолютную погрешности.

а=5,73 5:1,23≈4,66 (оставим 3 значащих цифры, т.к. наименьшее число верных

значащих цифр равно 3.

=0,00009+0,0041≈0,0042≈0,4%

∆a=δ_a×a=4,66×0,0042=0,02

Ответ: а=4,66±0,02

Если ответ записать с верными значащими цифрами, то необходимо произвести округлении, т.к. 0,02>0,005, тогда а=4,66≈4,7

Δа=Δа+Δ_окр=0,02+0,04=0,06. Тогда а=4,7±0,06

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

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

Пусть функция f(x) дифференцируема в некоторой окрестности приближенного значения аргумента х, а е_х - абсолютная ошибка значения аргумента. Тогда абсолютная ошибка значения функции e_f=|f(x+Ax)- f(x)| Поскольку на практике ошибка e_f обычно мала по сравнению со значением х, воспользуемся приближенным равенством: e_f ≈|df |=|f '(х)| ×е_х. Заменим е_х на Δх. Это означает, что можно принять

Δf = |f '(x)|-Δx.

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

функция f(x)	абсолютная погрешность Δf(x)	относительная погрешность  δf(x)
ап	n×an-1×∆a	n×δa
а2	2×a×∆a	2×δa
		×δa
		×δa
		δa
sinx	|cosx|×∆x	|x× ctgx|×δx
cosx	|sinx|×∆x	|x× tgx|×δx
tgx		× δx
lnx
lgx
ex	ex×∆x	|x|×δx
arcsinx		× δx
arccosx		× δx
arctgx		× δx
xy	xy	|y×lnx|×δy+|y|× δx

5.                 Правила подсчета цифр

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

1.     обеспечить заданную точность результата;

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

Правила подсчета, данные В.М. Брадисом.

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

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

3.     При возведении приближенного числа в квадрат или куб в результате следует сохранить столько значащих цифр, сколько их в приближенном числе.

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

5.     При вычислении промежуточных результатов следует сохранить на одну цифру больше, чем рекомендуют правила 1-4. в окончательном результате эта «запасная» цифра отбрасывается.

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

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

Эти правила дают в предположении, что компоненты действий содержат только верные цифры и число действий невелико.

Пример. Вычислить x=. Определить погрешность результата.

а=2,754±0,001

b=11,7±0,04

с=10,536±0,002

d=6,32±0,008

m= 0,56±0,05

Решение.

а=2,754≈2,75 т.к. в числе 3 цифры.

a+b=2,75+l 1,7=14,45

∆_а+ь=∆а+∆b+∆_окр=0,001+0,04+0,004=0,045

c=10,536≈10,54

c-d=10,54-6,32=4,22

∆_с-d=∆с+∆d+∆_окр=0,002+0,008+0,004=0,014

x==0,4543923≈0,45

δ_x==0,0031+0,0893+0,0066=0,099

∆x=δx×x=0,099- 0,45 = 0,04455≈ 0,04

Ответ: х=0,45±0,04

6. Упражнения.

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

y=                   y=

2.      Пользуясь правилами подсчета цифр, вычислить:

S=

где:    l=2,73; а=0,152; b=0,328

Перечень источников:

1. Вержбицкий В.М. Основы численных методов: учебник для вузов. М.: Высшая школа, 2002. - 302 с.

2. Лапчик М.П., Рагулина М.И.. Численные методы: учебное пособие для студентов вузов/.-М.: Издательский центр «Академия», 2004.- 362 с.

Раздел 2. Численные методы (44 часа)

Тема 2.1. Приближенное решение алгебраических и трансцендентных уравнений (12 часов)

Тип лекции: текущая

План:

1. Алгебраические и трансцендентные уравнения

2. Графический метод отделения корней

3. Аналитический метод отделения корней

4. Уточнение корней

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

6. Метод хорд

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

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

9. Упражнения

10. Вопрос для самостоятельного изучения:

-уравнение с одним неизвестным

-подготовка реферата по теме: «Вклад Ньютона в развитие численных методов»

1. Алгебраические и трансцендентные уравнения

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

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

Уравнение с одним неизвестным можно записать в виде

f(x)=0 или φ(x)=g(x) (1)

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

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

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

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

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

Отделение корней алгебраических и трансцендентных уравнений.

Пусть имеется уравнение вида f(x)=0, где f(x)- алгебраическая или трансцендентная функция.

Решить такое уравнение - значит установить, имеет ли оно корни, сколько корней, и найти значение корней.

Решение указанной задачи в общем случае начинается с отделения корней, т.е. с установления:

1)    количество корней;

2)    наиболее «тесных» промежутков, каждый из которых содержит только один корень.

Отделение корней можно произвести двумя методами - графическим и аналитическим.

2. Графический метод отделения корней

Строят график функции y=f(x) для уравнения вида f(x)=0 или представляют уравнение в виде cp(x)=g(x) и стоят графики функции y=f(x) и y=g(x). Значения действительных корней уравнения является абсциссами точек пересечения графиков функций y=f(x) с осью Ох или абсциссами точек пересечения графиков функций у=φ(х) и y=g(x). По графику определяются два числа а и Ь, между которыми заключен корень.

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

Замечание:

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

2.     Аналитический метод отделения корней

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

Т1. Если функция f(x) непрерывна на [a;b] и принимает на концах этого отрезка значения разных знаков, то внутри отрезка [а;b] существует по крайне мере один корень уравнения f(x)=0.

Т2. Если функция f(x) непрерывна и монотонна на отрезке [а;b] и принимает на концах этого отрезка значения разных знаков, то внутри отрезка [а;b] содержится корень уравнения f(x)=0, этот корень единственный.

Т3. Если функция f(x) непрерывна на [а;b] и принимает на концах этого отрезка значения разных знаков, а производная f ' (x) сохраняет постоянный знак внутри отрезка, то внутри отрезка [а;b] существует корень уравнения f(x)=0 и притом единственный.

Функция y=f(x) называется монотонной в заданном интервале, если при любых х₂> х₁ из этого интервала она удовлетворяет условию f(x₂)>f(x₁) (монотонно возрастающая функция) или f(x₂)<f(x₁) (монотонно убывающая функция).

Пусть на отрезке [а;b] функция f(x) непрерывна и принимает на концах отрезка значения разных знаков, а производная f ' (x) сохраняет постоянный знак на интервале (а;b). Тогда если во всех точках интервала (а;b) первая производная положительна        (f '(x)>0), то функция f(х) в этом интервале возрастает.(см. рис. а, в)

Если во всех точках интервала (а;b) первая производная отрицательна (f ' (x)<0), то функция в этом интервале убывает, (см. рис. б, г)

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

1)    находят f '(x) - первую производную;

2)    составляют таблицу знаков функции f(x), полагая х равным критическим значениям и граничным значениям;

3)    определяют интервалы, на концах которых функция принимает значения противоположных знаков.

Пример. Отделить корни уравнения  2^х - 5х - 3 = 0.

D(f(x)=R

1) f ' (х)=2^x×ln2-5                    х×ln 2 = ln 5 - ln ln 2

2^x×ln2-5=0                                   

2^x×ln2=5

2^x=                                              x=

2)

X	- ∞	2	3	+∞
f(x)	+	-	-	+

уравнение имеет два корня

3)

X	-1	0	1	2	3	4	5
f(x)	+	-	-	-	-	-	+

корни уравнения находятся в промежутках (-1;0) и (4;5)

4. Уточнение корней

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

Пусть дано уравнение f(x)=0. Требуется найти корень этого уравнения ζ  с точностью ε.

Будем считать, что ζ, отделен и находится на отрезке [а;b]. Числа а и b- приближенные значения корня ζ, соответственно с недостатком и с избытком.

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

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

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

Пусть уравнение f(x)=0 имеет на отрезке [а;b] единственный корень, причем функция f(x) на этом отрезке непрерывна. Разделим отрезок [а;b] пополам точкой

c=

Если f(x)≠c, то возможны два случая:

1.  f(x) меняет знак на отрезке [а;с];

2.            f(x) меняет знак на отрезке [b;с].

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

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

Пример. Методом половинного деления найти корень уравнение х³ + 2х -3 = 0 с точностью   ε = 0.001.

После отделения корней получилось, что корень уравнения лежит в следующих интервалах: (-3;-2), (-2;-l), (0;l).

Рассмотрим интервал (- 3;-2), для удобства составим таблицу. Знаки «-» и «+» в верхних индексах а_п и b_п означают, что f(a_n) < 0 и f(b_n) > 0

n	a-n	b+n	xn=	x3n	3x2n	f(xn)
0	-3	-2	-2.5	-15.625	18.75	0.125
1	-3	-2.5	-2.75	-20.8	22.689	-1.111
2	-2.750	-2.5	-2.625	-17.99	20.67	-0.320
3	-2.625	-2.5	-2.563	-16.84	19.701	-0.139
4	-2.563	-2.5	-2.532	-16.23	19.233	0.003
5	-2.563	-2.532	-2.548	-16.54	19.479	-0.071
6	-2.548	-2.532	-2.540	-16.39	19.356	-0.034
7	-2.540	-2.532	-2.536	-16.31	19.293	-0.014
8	-2.536	-2.532	-2.534	-16.27	19.263	-0.007
9	-2.534	-2.532	-2.533	-16.25	19.248	-0.002
10	-2.533	-2.532

Итак, корень уравнения х ≈-2,532

Пример: решить графическим методом отделения корней

Уравнение: х²-sinx-1=0

Представим в виде: х²=1+ sinx

x	π	0
y	2	1	1

     

ξ₁Î [-1; 0]

ξ₂Î [-1; П]

x²e^x=π                  Df: xÎR сколько корней и где они расположены.

f(x) = x²e^x- π

f `(x) = (x<sup>2</sup>)`×e^x + (e^x )`× x²=2x e^x+ e^x ×x²=x e^x(2+x)

x e^x(2+x)=0

f:	-∞	-2	0	+∞
	-	-	-	+

x e^x=0        2+x=0

x=0             x=-2

f(-2)=(-2)²×e^(-2)= <0

f(0)=lim x²e^x-π=+∞ > 0

             ^x→+∞

f:	-∞	-2	0	1	2	+∞
	-	-	-	-	+	+

mÎ [1; 2]

Пример: Отделить корни уравнения 2^х-5х-3=0 аналитическим методом.

Решение: Обозначим f(x)= 2^х-5х-3, D_fÎR

f`(x)= 2^хln2-5

2^хln2-5=0

2^хln2=5

2^х=

x≈2,85

Составим таблицу знаков функции f(x) полагая х равным: а) критическим значениям (корень произв.) или ближайшим к ним б) граничным значениям из ОДЗ.

х	-∞	-2	3	+∞
Sign f(x)	-	-	-	+

lim 2^x-5x-3=>0

^x→-∞

lim 2²-5×2-3<0

^x→2

lim (-2)²-5×(-2)-3<0

^x→-2

f:	-2	-1	0	1	2	3	4	5
	+	+	-	-	-	-	-	+

m₁Î [-1; 0]

m₂Î [4; 5]

6. Метод хорд

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

Пусть дано уравнение f(x)=0, корень находится на отрезке [а;b]. Идея метода хорд состоит в том, что на достаточно малом промежутке [а;b] дуга кривой y=f(x) заменяется стягивающей её хордой. В качестве приближенного значения корня принимается точка пересечения хорды с осью Ох.

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

f ' (x)×f '' (x)>0

Пусть дано уравнение y(x)=0, где f(x) – непрерывная функция, имеющая в интервале (а, b) производные первого и второго порядка.

Корень считается отделенным и находится на [а, b], то есть f(a)×f(b) <0

Уравнение хорды, проходящей через точки А и В, имеет вид

у=0  , следовательно х_х=а-

Уравнение хорды, проходящей через точки А₁ и В

x₂=x₁- и так далее, получаем, x_n+1=x_n-

Тогда получаем

x_n+1=x_n-

l)f(a)<0, f(b)<0, f ' (x)>0, f '' (x)>0

2) f(a)>0, f(b)<0, f ' (x)<0, f '' (х)<0

Рассмотрим случай, когда производные имеют разные знаки f ' (x)×f '' (x) <0

x₁=b-      x₂=x₁- и так далее.

Тогда получаем

x_n+1=x_n-       1) f(a)>0, f(b)<0, f ' (x)<0, f ''(х)>0

         2) f(a)<0, f(b)>0, f ' (x)>0, f ''(x)<0

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

Если f(b)×f ''(х)>0, то неподвижен конец b, используют формулу

x_n+1=x_n-

Если f(a)×f "(х)>0, то неподвижен конец а, используют формулу

x_n+1=x_n- 

При оценке погрешности приближения можно пользоваться формулой

|ξ-x_n|<|x_n-x_n-1| или |ξ-x_n|< , где m=

Справедлива при условии М<2m, ξ – точное значение корня, x_n-1, x_n – приближение к нему m=

Пример. Методом хорд уточнить до ε=0,001 корень уравнения х³ + 3х -3 = 0, если корни уравнения на отрезке [0;2].

a=0  b=2   f(x) = x³ +3х² -3,     f ' (x) = 3х² + 6х,    f"(x) = 6x + 6

f(a)= -3<0

f(b)=8+l2-3=17>0

f '' (x)>0 на отрезке [0;2]

f(b) f '' (x)>0, следовательно x_n+1=x_n-

Вычисления удобно производить в таблице:

xn+1	xn	xn3	xn2	3хn2	f(xn)	2-хn	А	В
0,3	0	0	0	0	-3	2	-6	20
0,533218	0,3	0,027	0,09	0,27	-2,703	1,7	4595	19,703
0,687166	0,533	0,151	0,2841	0,85227	-1,996	1,467	-2,929	18,996
0,777591	0,687	0,324	0,472	1,41591	-1,26	1,313	-1,654	18,26
0,827205	0,778	0,471	0,6053	1,81585	-0,713	1,222	-0,872	17,713
0,852819	0,827	0,566	0,6839	2,05179	-0,383	1,173	-0,449	17,383
0,866007	0,8528	0,62	0,7273	2,1818	-0,198	1,1472	-0,227	17,198
0,872679	0,866007	0,649	0,75	2,2499	-0,101	1,134	-0,114	17,101
0,87603	0,872679	0,665	0,7616	2,28471	-0,051	1,1273	-0,057	17,051
0,87603	0,872679	0,665	0,7616	2,28471	-0,051	1,1273	-0,057	17,051
0,877708	0,87603	0,672	0,7674	2,30229	-0,025	1,124	-0,029	17,025
0,878547	0,877708	0,676	0,7704	2,31111	-0,013	1,1223	-0,014	17,013
0,878967	0,878547	0,678	0,7718	2,31553	-0,006	1,1215	-0,007	17,006
0,879176	0,878967	0,679	0,7726	2,31775	-0,003	1,121	-0,004	17,003
0,879281	0,879176	0,68	0,773	2,31885	-0,002	1,1208	-0,002	17,002
0,879333	0,879281	0,68	0,7731	2,31941	-8Е-04	1,1207	-9Е-04	17,001

7. Метод касательных (метод Ньютона).

Геометрический смысл метода Ньютона состоит в том, что дуга кривой y=f(x) заменяется касательной к этой кривой.

Полагая у=0, x=x₁ , получаем

0=f(b)-f ' (b)(x₁b) следовательно   f ' (b)(x₁b)= -f(b),

x₁-b=-     x₁=b-

Теперь корень находим на отрезке [а;x₁]

x₂=x₁- и так далее, получаем x_n+1=x_n-

Получаем последовательность приближений х₁ х₂, ..., х_n, каждый последующий член ближе к корню ξ.

Если касательную провести в точке В, то она пересечет Ох в точке, не принадлежащей отрезку [а;b]. Поэтому проведём касательную к кривой y=f(x) в точке А.

y-f(a)=f ' (a)(x-a)

Полагая у=0, х=x₁, получаем   x₁=a-

Применяя снова метод Ньютона, получаем

x₂=x₁- и так далее, получаем x_n+1=x_n-

Получаем последовательность приближений х₁ х₂, ..., х_n, каждый последующий член ближе к корню ξ.

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

Правило: за исходную точку следует выбирать тот конец отрезка [а;b] в котором знак функции совпадает со знаком второй производной

1)  f(b)- f ''(х)>0, следовательно x₀=b

2) f(a)- f ''(х)>0, следовательно х₀=а

Пример:	методом касательных найти корень уравнения				х3+х-3 = 0
xn	xn3	f(x)	f '(хn)	f(x)/f ' (хn)	хn+1
2	8	7	13	0,538461538	1,461538462
1,461538	3,121985	1,583523	7,408284028	0,213750308	1,247788154
1,247788	1,942775	0,1905635	5,670925832	0,033603589	1,214184565
1,214185	1,790005	0,0041891	5,422732474	0,000772501	1,213412064
1,213412	1,78659	2.174Е-06	5,417106511	4.01238Е-07	1,213411663
1,213412	1,786588	1.288Е-09	5,417103592	2.3777Е-10	1,213411663

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

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

Если f ' (x) f '' (х)>0, то метод хорд дает приближения корня с недостатком, а метод касательных- с избытком.

Если f ' (x)> f '' (х)<0, то методом хорд получаем значение корня с избытком, а методом касательных - с недостатком.

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

а < < ξ <  <b

где  - приближенное значение с недостатком;

 -приближенное значение с избытком.

Вычисления следует вести в таком порядке:

1)      Если f ' (x)× f '' (х)>0 то со стороны конца а лежат приближенные значения корня, полученные по методу хорд, а со стороны конца b - значения, полученные по методу касательных и тогда

a_n+1=a_n-    и     b_n+1=b_n-

2)      Если же f ' (x)× f '' (х) < 0 , то со стороны конца а лежат приближенные значения корня, полученные по методу касательных, а со стороны конца b -значения, полученные по методу хорд и тогда

a_n+1=a_n-    и    b_n+1=b_n- 

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

|-x_п| <ε

За приближенное значение корня следует принять ξ=, где  - приближенное значение с недостатком;  - приближенное значение с избытком.

Пример: комбинированным методом хорд и касательных уточнить до 0,001 корни уравнения х³ + 3х² - 24х + 1 = 0.

Решение:

1) Отделим корни аналитически. Имеем f(x) = x³ +3х - 24х + 1

f ' (x) = 3х²+ 6х-24 , т.е. корни производной х₁ = - 4 и х₂ = 2 .

Составим таблицу знаков функции:

x	-∞	-4	2	∞
знак f(x)	-	+	-	+

Данное уравнение имеет три действительных корня:

x₁ Î (-∞,-4), х₂ Î (-4,2), х₃ Î (2,+ ∞).

Уменьшим промежутки нахождения корней до длины равной 1:

x	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4
знак f(x)	-	+	+	+	+	+	+	+	-	-	-	+

Итак x₁ Î (-7,-6), х₂ Î (0,1), х₃ Î (3,4)

2) Уточним комбинированным методом хорд и касательных корень, лежащий в интервале (-7,-6). Имеем f(-7) = -27 < 0 ; f (-6) = 37 > 0 и

f'(x) = 3х² + 6х - 24 _; f "(x) = 6х + 24 < 0 _; f'(x) × f "(x)< 0. Для расчетов применяем формулы:

a_n+1=a_n-    и    b_n+1=b_n- то есть

a_n+1=a_n+∆a_n, где ∆a_n = 

b_n+1=b_n+ba_n, где ∆b_n =

(a_n и b_n - приближенные значения корня соответственно с недостатком и с избытком). Здесь а₀= а= -7   и  b₀ - b = -6 .

Вычисления удобно провести в таблице

n	an	bn- -an	a2n	a3n	f(an)	f' (an)	f(bn)- f(an)	∆an	an+1
	bn		b2n	b3n	f(bn)			∆ bn	bn+1
0	-7	1	49	-343	-27	81	64	0.333	-6.667
	-6		36	-216	37			-0.578	-6.578
1	-6.667	0,089	44,449	-296,34	-1,985	73,345	6,037	0,027	-6,640
	-6.578		43,270	-284,63	4,052			-0,060	-6,638
2	-6,640	0,002	44,090	-292,75	-1,12
	-6,638		44,063	-292,49	0,011

Следовательно, ξ₁ ≈ -6,639

9. Упражнения

1.     Отделить корни графически и уточнить их до 0,001 методом хорд:

 x³ + 8х - 6 = 0 и х³ + 10х - 9 = 0

2.     Методом касательных с точностью до 0,001 найти корни уравнения  x³-6x²+9x-3 = 0 и x³ -12х-8 = 0

3.     Комбинированным методом хорд и касательных с точностью до 0,001 найти корни уравнений: x³+6x-5 = 0 и  2x-lnx-l = 0

4.     Отделить корни уравнения аналитически    х³ -х + 1 = 0 и 2^х-4х = 0

5.     Отделить корни уравнения графически х³ +х-3 = 0 и lg x=

6. Методом половинного деления найти решение уравнения.

х⁴ + 5х - 3 = 0 с точностью 8=0,001

х × sin х -1 = 0 с точностью 8=0,0001

Тема 2.2. Решение систем линейных уравнений ( 8 часов)

Тип лекции: текущая

План:

1 Постановка задачи

2 Метод Гаусса

3 Вычисление определителей и обращение матриц на основе метода Гаусса

4 Метод простой итерации

5 Метод Зейделя

6 Упражнения

7. Вопрос для самостоятельного изучения

-метод Холецкого ( метод квадратных корней )

-подготовка исторической справки о биографии учёных – математиках: Гауссе, Зейделе

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

1 Постановка задачи

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

Прежде чем перейти к рассмотрению методов решения систем линейных алгебраических уравнений (СЛАУ), вспомним основные понятия, касающиеся данной темы.

Общий вид системы  n  линейных алгебраических уравнений с  n  неизвестными имеет вид:

(1)

или в матричной форме , т.е.

Aх=B,

где: A={a_ij} - квадратная матрица размерности  n´n ;

       x={x_i} ^T  - вектор неизвестных n-го порядка;

      B={b_i} ^T  - заданный вектор правых частей системы (); T – операция транспонирования. Далее будем считать матрицу невырожденной (неособенной), т.е. detA¹0, система будет иметь единственное решение. Поставленная задача часто называется первой задачей линейной алгебры.

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

Под точным решением СЛАУ будем понимать вектор (или точку) , координаты которого при подстановке в систему (1) обращают каждое уравнение системы в верное равенство.

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

Методы решения задач линейной алгебры можно разделить на точные и итерационные.

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

В дальнейшем нам понадобится понятие нормы вектора и матрицы.

В векторном n-мерном линейном нормированном пространстве можно ввести следующие нормы вектора:

кубическая:

октаэдрическая:

евклидова (в комплексном случае — эрмитова):

Рассмотрим квадратную матрицу A и связанное с ней линейное преобразование y=Ax, где  (Lⁿ — n-мерное линейное нормированное пространство). Норма матрицы определяется как действительное неотрицательное число, характеризующее это преобразование равное:

Заметим, что норму матрицы (2.3) называют подчиненной норме вектора. Говорят, что норма матрицы A согласована с нормой вектора x, если выполнено условие

Нетрудно видеть, что подчиненная норма согласована с соответствующей метрикой векторного пространства.

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

2 Метод Гаусса

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

Рассмотрим прямой ход. Шаг k=1. Подвергнем систему (1) следующему преобразованию. Считая, что  (ведущий элемент), разделим на него коэффициенты первого уравнения, получим:

,

(2)

где  и

С помощью уравнения (2) исключим во всех уравнениях системы (1), начиная со второго, слагаемые, содержащие х₁. Для этого умножаем обе части уравнения (2) последовательно на а₂₁, а₃₁,…,а_n1 и вычитаем соответственно из второго, третьего, …, n-го уравнения системы (1).

Тогда матрица системы будет иметь вид:  (× - ненулевые элементы)

Далее будем работать (не трогая первого уравнения) с полученной системой:

где .

Шаг k=2,3, …n -1. Аналогично преобразуем полученную систему, в результате этого преобразования получим систему с верхнетреугольной матрицей с единицами по диагонали, которая эквивалентна системе (1) и легко решается:

,

(3)

где на k-ом шаге элементы матрицы рассчитываются по формулам:

и , ,

(4)

причем

Обратный ход. Из последнего уравнения находим x_n, подставляя x_n в предпоследнее уравнение, найдем x_n-1, затем x_n-2 и т. д. до x₁, которое находим из первого уравнения системы, когда уже известны , в результате получаем рекуррентные формулы для поиска решения:

где коэффициенты  и правые части  ,i=1..n – коэффициенты матрицы (3), обозначенной как .

Замечания.

1 Реализация прямого хода метода Гаусса требует  - арифметических операций, а обратного  - арифметических действий.

2 При реализации на ЭВМ метода Гаусса рекуррентные формулы (4) удобнее реализовать для расширенной матрицы, состоящей из исходной матрицы А и правых частей системы.

Рассмотренный метод Гаусса называется методом единственного деления в смысле отсутствия выбора ведущих элементов.

Ведущими элементами метода Гаусса называют коэффициенты а₁₁, а₂₂⁽¹⁾,а₃₃⁽²⁾, …, a_nn^(n-1). На каждом шаге предполагалось, что a_kk^(k-1)≠0, если окажется, что это не так, то метод не применим. Или если коэффициент        a_kk^(k-1)≠0 мал, то после деления на этот элемент и вычитания k-го уравнения из последующих возникают большие погрешности округления. В этом случае нужно применять метод Гаусса с выбором главного элемента (по столбцу, по строкам или по всей матрице). Проще всего использовать метод Гаусса с выбором главного элемента по столбцу (его называют методом Гаусса-Жордана). В этом методе в качестве ведущего элемента используют максимальный по модулю элемент столбца, для этого на каждом k-м шаге уравнения переставляют так, чтобы на главной диагонали оказался наибольший по модулю элемент k-го столбца.

3 Вычисление определителей и обращение матриц на основе метода Гаусса

Без вывода приведем формулу вычисления определителя исходной матрицы

,                                               (5)

где  - ведущие элементы схемы единственного деления.

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

Алгоритм метода Гаусса и вычисления определителя можно оформить в виде схемы

,

(6)

где квадратной скобкой обозначено тело цикла, начальное и конечное значения которого заданы слева.

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

(7)

Пример 1. Решить систему линейных уравнений , заданную матрицами  и , методом Гаусса найти det A.

Для проведения прямого хода метода Гаусса воспользуемся схемой (6) и результаты вычислений оформим в виде схемы:

k	i	j	Вычисления
1
		1 2 3 4
	2
		2 3 4
	3	2 3 4
После первого шага получена матрица
2
		2 3 4
	3
		3 4
После второго шага получена матрица
3
		3 4
После третьего шага получили окончательный вид матрицы

Итак, определитель равен -9. В результате обратного хода найдем по рекуррентным формулам решение системы

, ,

Получили решение .

Схема единственного деления может использоваться также и для вычисления элементов матрицы , обратной для невырожденной матрицы А. Способ получают из определения , где Е — единичная матрица. Искомую матрицу  и единичную матрицу представляют в виде совокупности векторов-столбцов:

,

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

(8)

Решение каждой системы дает соответствующий столбец обратной матрицы.

Пример 2. Найти обратную матрицу для матрицы из предыдущего примера.

Для этого нужно решить три системы:

, , .

Решаем методом Гаусса, получившиеся три вектора решения

,  и  являются векторами столбцами обратной матрицы, т.е.

4 Метод простой итерации

Приведем систему (1) к равносильной ей системе вида . В развернутом виде новая система выглядит так:

(10)

или в сокращенной записи  (i=1,2,…,n). О системе со структурой (10) говорят, что она «приведена к нормальному виду».

Тогда используя итерационную формулу

(11)

и выбрав начальную точку  (обычно за начальное приближение выбирают вектор с координатами  (i=1,2,…,n) из системы (10)), строят итерационную последовательность приближений . Итерационный процесс прекращают при выполнении условия

(12)

или при выполнении более простого условия . Тогда приближение , найденное на (k+1)-й итерации принимают за приближенное решение с точностью .

Замечания.

1 Процесс (11) называют параллельным итерированием, т.к. для вычисления (k+1)-го приближения всех неизвестных используются вычисленные ранее их (k)-е приближения.

2 Число итераций k , необходимых для достижения заданной точности , можно узнать заранее из неравенства

Достаточное условие сходимости

Теорема. Если какая-либо норма матрицы  меньше 1, то метод простых итераций сходится.

Т.е. для сходимости операции в методе (10) достаточно выполнение условия , тогда достаточные условия примут следующий вид:

;  ;   . Метод сходится тем скорее, чем меньше .

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

метод простых итераций сходится для матриц А  системы  Aх=B , у которых диагональные элементы велики по сравнению с внедиагональными, те.

 или .

Замечания.

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

2 Вполне возможно, что для некоторой конкретной системы метод итерации окажется неприменимым.

3 Mетод простой итерации занимает ≈ 2n²*I арифметических операций, где I — число приближений, необходимое для достижения заданной точности. Значит, при I<n/3 метод итераций становится предпочтительнее метода Гаусса. В реальных задачах, в основном, I<<n.

Преобразование системы к эквивалентному виду

Рассмотрим способы преобразования системы (1) к виду (10).

1 Можно переписать систему  в виде  (х+Ах)=х+b, а потом

х=-Ах+х+b, т.е

2 Систему  умножить на матрицу , где  - матрица с малыми по модулю элементами, тогда , т.е

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

Пример 4. Для данной системы линейных алгебраических уравнений  найти первое приближение по методу Якоби и проверить условие окончания итераций при e=0,01.

Решение.

Вычисления ведем с одной запасной цифрой.

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

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

 

2 Далее достаточно из первого уравнения выразить переменную x₁ , из второго переменную x₂ , а из третьего - переменную x₃ , в результате получим систему:

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

.

Рассчитаем норму матрицы по формуле   , для этого складывая элементы по столбцам, получим

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

4 Затем составим итерационные формулы

, k=0,1….

5 Подставляя в эту систему нулевое приближение вместо переменных , найдем первое приближение к решению, причем за нулевое приближение примем вектор = (1,75;1,5;4/3).

.

Таким образом, получили первое приближение .

6 Проверим условие окончания итераций по формуле

, иначе . Найдем сначала модули разностей каждых из соответствующих координат

, теперь найдем максимальное из полученных значений

, условие не выполнено, следовательно, необходимо продолжить итерации.

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

Метод Зейделя – это усовершенствованный метод простых итераций. Идея модификации состоит в том, что при вычислении очередного (k+1)-го приближения к неизвестному х_i при i>1 используют уже найденные (k+1)-е приближения к неизвестным х_i, x_i-1,…,x₁, а не k-е приближения, как в методе простых итераций.

Итерационная формула имеет вид:

, i=1..n

(13)

А именно, если найдено приближение , то следующее приближение определяется из системы соотношений:

(14)

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

Кроме того метод Зейделя всегда сходится для нормальных систем линейных алгебраических уравнений, т.е. таких систем, в которых матрица А симметричная положительно определенная.

Замечания. 

1 Всякая система  Ax=b  с невырожденной матрицей может быть приведена к системе с симметричной положительно определенной матрицей умножением обеих частей уравнения на матрицу А^Т . В самом деле система А^ТАх=А^Тb эквивалентна исходной , матрица А^ТА – симметричная, так как А^ТА= (А^ТА)^Т , и положительно определена, так как (A^TAx,x)=||Ax||²>0 при х≠0. По возможности стараются избегать симметризации, поскольку она часто приводит к ухудшению сходимости итерационных процессов.

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

Пример 5. Для системы уравнений, рассмотренной в примере 1, найти первое приближение по методу Зейделя и проверить условие окончания итераций при e=0,01

Решение.

1 Как было установлено в примере 4, после приведения исходной системы к виду

условие сходимости выполняется.

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

3 Составим итерационные формулы

, k=0,1….

4 Найдем так же как и и методе простых итераций :

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

Аналогично при вычислении  используем уже найденные приближения  и :

.

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

, теперь найдем максимальное из полученных значений

. Видно, что условие не выполнено, следовательно, необходимо продолжить итерации.

6. Упражнения

Решить системы линейных уравнений:

а)                    б)

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

7.  Метод Холецкого ( метод квадратных корней )

Довольно часто на практике встречаются системы c симметричной матрицей, для которых экономичнее применять метод квадратного корня или по-другому метод Холецкого.

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

Дана система вида (1): , где А – симметричная матрица, ее можно представить в виде:

,  

где Т- верхняя треугольная матрица с коэффициентами   , рассчитанными по формулам

, , , ,  ,

(9)

 – матрица, транспонированная к Т.

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

,

, где  вектор х – искомое решение. Для их решения легко получить рекуррентные формулы   - для первой системы, и   - для второй системы.

Замечания.

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

2.            Возможно переполнение - если угловые элементы близки к нулю.

Пример 3. Решить систему линейных уравнений , заданную матрицами  и  методом Холецкого.

1 Рассчитаем матрицу  Т по формулам (9):

, ,

,

     

2 Далее решая систему линейных алгебраических уравнений   получим вектор её решений  y=(2,475;2,349;1,535), который подставим в систему  , её решение  x=(1;1;1) и является искомым решением.

Тема 2.3. Интерполирование и экстраполирование ( 8 часов)

Тип лекции: текущая

План:

1 Постановка задачи аппроксимации функций

2. Интерполяционный многочлен Лагранжа

3. Конечноразностные интерполяционные формулы

4. Интерполяционные полиномы Ньютона

5. Вторая интерполяционная формула Ньютона

6. Вопрос для самостоятельного изучения:

-подготовка исторической справки о биографии учённых – математиках : Ньютоне, Лагранже;

 творческая  работа по интерполированию и экстраполированию.

1. Постановка задачи аппроксимации функций

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

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

Пусть на отрезке [a,b] задана функция у=f(x) своими n+1 значениями , в точках . Т.е.

:

(1)

Точки называются узлами.

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

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

В такой постановке эта задача решается неоднозначно.

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

Функция  называется интерполирующей или интерполяционной для  на , если ее значения , ,…, в заданных точках , называемых узлами интерполяции, совпадают с заданными значениями функции , т.е. .

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

Простейший способ интерполяции — кусочно - линейная, требующая минимальных требований на гладкость функции f(t). При таком способе интерполяции соседние точки (t_n, f_n) и (t_{n + 1}, f_{n + 1}) соединяют отрезками прямых

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

Легко представить, что таких графиков  множество.

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

(2)

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

Пусть многочлен   представлен в виде

(3)

он является линейной комбинацией некоторых базисных функций   с коэффициентами , которые находятся в зависимости от вида приближения. Многочлен Ф_m(х) называют обобщенным многочленом по системе функций j₀(х), j₁(х),… ,j_m(х), а число m – его степенью.

Для того чтобы обобщенный многочлен был интерполяционным необходимо выполнение условия (2), тогда получаем систему уравнений:

или в векторной форме Ac=y

где

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

Теорема (доказывается в курсе линейной алгебры.) Для того чтобы система функций была линейной независимой в точках t₀, ..., t_n, необходимо и достаточно, чтобы определитель матрицы Грамма

был отличен от нуля. Здесь каждый элемент матрицы Грамма имеет вид

В случае, если система функций ортогональна на множестве точек , решение задачи интерполяции значительно упрощается (напомним, что система функций является ортогональной на множестве точек , если при и при k = j для всех k = 0, 1, ..., N; j = 0, 1, ..., n).

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

Примером ортогональной системы являются показательные функции на множестве точек t_j = {j / N}, j = 0, 1, ..., N (на отрезке [0, 1]).

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

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

Для функций непрерывных на , расстояние можно рассчитать по формулам:

,

и др.

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

Часто процедура аппроксимации связана с другим критерием:

,

на его основе создан способ аппроксимации, называемый методом наименьших квадратов.

2. Интерполяционный многочлен Лагранжа

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

Ln(x )=a0+a1 x+a2 x2+…+anxn,

(4)

где а неизвестные постоянные коэффициенты.

Учитывая, что этот многочлен должен удовлетворять условию (2), т.е.

(5)

получают систему линейных алгебраических уравнений:

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

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

, i= 0,1,…, n.

Необходимо его построить с учетом условий (5), для этого достаточно положить , а на многочлены  наложить условия

.

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

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

.

Таким образом, искомый интерполяционный многочлен Лагранжа принимает вид  

(6)

или в развернутом виде

      (7)

На практике часто используется линейная и квадратичная интерполяция:

; .

(8)

Интерполяционный многочлен Лагранжа для равноотстоящих узлов имеет вид:

(9)

где q=(x-x₀)/h, h-шаг интерполирования,

Оценка погрешности

Погрешность многочлена Лагранжа можно оценить, если известна (n+1) – я производная функции f(x).

Пусть  , где  –погрешность;  f(x) - точное значение функции в точке х; - приближенное значение, полученное по полиному Лагранжа.

Тогда

(10)

где , , x[a,b], причем , .

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

x	-1	0	1	2
y	1.8	2.4	2.2	2

Подставим значения из таблицы в формулу (8) для L₂(x) :

После преобразования получим многочлен:   L₂(x)=-0,4x²+0,2x+2,4

3.  Конечноразностные интерполяционные формулы

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

Конечные разности

Введем понятие конечной разности.

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

В системе точек х₀, х₁,…, х_n  всего n конечных разностей первого порядка:

, , …, .

Из них получают (n-1) конечных разностей  второго порядка:

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

, где k=1..n,

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

y

1.8

2.4

2.2

2

Составим таблицу конечных разностей.

0	1.8	0.6	-0.8	0.4
1	2.4	-0.2	-0.4
2	2.2	-0.2
3	2

Приведем некоторые свойства конечных разностей.

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

, , ,…  , .

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

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

Интересно следующее свойство: если конечные разности  n - го порядка функции f(x) постоянны в любой точке x при различных фиксированных шагах h, то эта функция есть многочлен степени n. Это свойство позволяет выбрать оптимальную степень многочлена. Если , где  -  предельная абсолютная погрешность значений функции , то эти и последующие конечные разности не несут никакой информации о функции и их не следует учитывать, тогда за порядок многочлена следует принять n=k-1 .

4. Интерполяционные полиномы Ньютона для равноотстоящих узлов

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

.

Найдем этот многочлен  в виде:

,

(11)

где а_i (i=0,1,…,n) – неизвестные коэффициенты, которые требуется найти.

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

1              Найдем а₀ , для этого положим , тогда , отсюда а₀=у₀.

2              Вычислим . Положим , тогда , подставим найденное  и выразим , .

3              Аналогично определим коэффициент а₂,

 , тогда , выразим , получим .

4              Можно доказать, что общая формула для искомых коэффициентов имеет вид:  (i=0,1,2,…,n).

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

(12)

Этот многочлен более точно аппроксимирует функцию вблизи x₀,  так как в каждое слагаемое многочлена входит разность (x-x₀) . Иногда первую интерполяционную формулу можно используют в другом виде:

,

(13)

где q=(x-x₀)/h, h-шаг интерполирования. Узел x₀  называют базовым для первой формулы. За базовый узел можно принять любой узел таблицы, после которого достаточно узлов для построения многочлена требуемого порядка, а в реальности порядок бывает не высоким. Однако очевидно, что в конце таблицы все же нужна другая формула.

5. Вторая интерполяционная формула Ньютона

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

(14)

Неизвестные коэффициенты а₀,а₁,…,а_n подбирают так, чтобы были выполнены равенства , (i=0,1,…,n) аналогично первому случаю, только узлы подставляются в обратном порядке , , …, . Коэффициенты в общем случае имеют вид  k=0,1,…, n.

Подставив  эти коэффициенты в формулу многочлена, получим вторую интерполяционную формулу Ньютона:

(15)

На практике используют формулу Ньютона в другом виде. Положим q=(x-x_n)/h. Тогда

.

(16)

Оценка погрешности

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

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

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

x	-1	0	1	2
y	1.8	2.4	2.2	2

Для первой формулы Ньютона подставим значения из таблицы и n=2 в формулу (12) для P_n(x) и преобразуем, получим:

Для второй формулы Ньютона подставим значения из таблицы и n=2 в формулу (15) для P_n(x) и преобразуем, получим:

Тема 2.4. Численное интегрирование ( 8 часов)

Тип лекции: текущая

План:

1. Введение в численное интегрирование

2. Определение квадратурной формулы.

3. Простейшие квадратурные формулы (формулы прямоугольников, трапеций, Симпсона).

4. Вопрос для самостоятельного изучения:

- Составные квадратурные формулы с постоянным и переменным шагом

1. Введение в численное интегрирование

Геометрический смысл простейшего определенного интеграла

(7.1)

от неотрицательной функции f(x)≥0 состоит в том, что значение I - это площадь криволинейной трапеции, ограниченной кривой y=f(x) , осью абсцисс и прямыми x=a, x=b (рисунок 1)

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

.

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

2. Определение квадратурной формулы

Пусть вещественная функция f(x) определена и ограничена на замкнутом интервале от [a;b]. Разобьем [a;b] на n частичных интервалов [x_i;x_i+1] , 0≤i≤n-1, x_n=b, x₀=a. Выберем в каждом частичном интервале произвольную точку ξ_i, x_i ≤ ξ_i ≤ x_i+1, и составим интегральную сумму (рисунок.1):

.

(7.2)

                      

x

Обобщим понятие интегральной суммы (7.2). Точки ξ_i, в которых вычисляются значения f(x), назовем узлами, а коэффициенты (x_i+1 - x_i) в (7.2) заменим некоторыми числами q_i, не зависящими от f(x) , называемыми весами. Тогда формула (7.2) заменяется следующей:

,

где a ≤ ξ_i ≤ b. Эта формула называется квадратурной суммой. Запишем интеграл (7.1) в виде

,

(7.3)

R в (7.3) называется погрешностью или остаточным членом квадратурной формулы.

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

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

, , .

3.     Простейшие квадратурные формулы (формулы прямоугольников, трапеций, Симпсона)

Приведем квадратурные формулы для одного интервала [x_i-1;x_i] , которые затем обобщаются на весь интервал [a;b] в виде составных квадратурных формул.

Формула прямоугольников. Пусть рассматривается интервал [x_i-1;x_i] и шаг h>0.

Предположим, что подынтегральная функция f(x) дважды непрерывно дифференцируема на [x_i-1;x_i], т.е.. Запишем соотношение (7.3) в виде

,

(7.4)

где взят один узел , соответствующий вес q=h. Получаемая квадратурная формула

(7.5)

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

Тогда погрешность квадратурной формулы прямоугольников R_i  имеет вид

,

(7.6)

где ,

Квадратурная формула прямоугольников (7.5) является точной для полиномов первой степени P₁(x)=a₀+a₁x.

Иногда на интервале [x_i-1; x_i] применяют формулы левых и правых прямоугольников вида  или . Нетрудно заметить, что эти формулы точны только для полиномов нулевой степени, т.е. констант.

Формула трапеций.

Пусть [x_i-1; x_i] - рассматриваемый интервал и h>0

Предположим, что . Запишем соотношение (7.3) в виде

,

(7.7)

где взяты два узла ξ₀=x_i-1, ξ₁=x_i и соответствующие веса q₀=q₁=h/2.

Получаемая квадратурная формула

(7.8)

f(0)

f(x)

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

,

(7.9)

где  ξ_i - некоторая точка интервала [x_i-1; x_i].

Так же как формула прямоугольников, квадратурная формула трапеций (7.8) точна для полиномов первой степени.

Формула Симпсона.

y

Пусть дан интервал [x_i-1; x_i] и шаг h>0

x

Предположим, что . Запишем соотношение (7.3) в виде

,

где взяты три узла ξ₀=x_i-1, ξ₁=x_i-1/2, ξ₂=x_i и соответствующие веса q₀=q₂=h/6, q₁=4/6*h. Получаемая квадратурная формула

(7.11)

называется квадратурной формулой Симпсона или формулой парабол. Последнее название связывается с тем, что (7.11) – формула интеграла  от параболы , поведенной через точки (A_i-1), (A_i-1/2), (A_i) плоскости (x;y).

Погрешность квадратурной формулы Симпсона R_i  имеет вид

,

(7.12)

где  ξ - некоторая точка интервала [x_i-1;x_i].

Из (7.12) следует, что квадратурная формула Симпсона точна для полиномов третьей степени.

Простейшие формулы следует применять лишь на малых интервалах, поскольку при увеличении h погрешность становится значительной. Это следует из формул (7.6), (7.9), (7.12). На конечных интервалах интегрирования обычно применяют составные квадратурные формулы.

4. Составные квадратурные формулы.

Для получения составных квадратурных формул нужно интервал [a;b] разбить точками x_i, 0≤i≤n, на n интервалов и на каждом частичном интервале  [x_i;x_i+1] записать простейшую квадратурную формулу для приближенного значения интеграла  . Затем следует просуммировать полученные выражения и получить квадратурную формулу для всего интервала [a;b]. Абсолютную погрешность R составной формулы находят суммированием погрешностей R_i на каждом частичном интервале.

Рассмотрим составные квадратурные формулы с постоянным шагом.

Одним из наиболее простых правил разбиения интервала [a;b] на частичные интервалы [x_i;x_i+1] является условие x_i+1- x_i=h, 0≤i≤n-1, x₀=a, x_n=b.

Шаг определяется равенством h=(b-a)/n.

Пусть f(x)ÎC²[a;b]. Тогда просуммируем формулы вида (5) на [a;b] получим составную квадратурную формулу прямоугольника

()

для которой справедлива оценка погрешности

, .

Аналогично суммируя формулы вида (7.7) на [a;b] получим составную квадратурную формулу трапеций

или по-другому

.

Справедлива оценка погрешности составной квадратурной формулы трапеций

.

Теперь пусть f(x)ÎC⁴[a;b], тогда суммируя формулы вида  (7.11) получим составную квадратурную формулу Симпсона

или в развернутом виде

.

Справедлива оценка погрешности

.

В случае переменного шага , составные квадратурные формулы принимают вид:

прямоугольника: ,

трапеций: ,

Симпсона: .

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

Тема 2.5. Численное решение обыкновенных дифференциальных уравнений( 10 часов)

Тип лекции: текущая

План:

1. Постановка задачи

2. Метод  Эйлера (частный случай метода Рунге-Кутта)

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

4. Вопрос для самостоятельного изучения:

-устойчивость разностных схем

-подготовка рефератов по теме: «Задачи, приводящие к дифференциальным уравнениям», «Дифференциальные уравнения в науке и технике».

1. Постановка задачи.

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

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

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

, .

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

Поскольку решением ОДУ является функция, то под численным решением задачи Коши будем понимать – поиск значений функции только в конечном числе дискретных точек (узлов сетки), а не на всем непрерывном отрезке. Значение функции, в какой либо промежуточной точке можно получить каким либо способом аппроксимации функции.

Рассмотрим задачу Коши для системы ОДУ. Пусть имеется n неизвестных функций , для которых имеет место n дифференциальных уравнений.

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

Можно записать систему в векторной форме, введем обозначения

, тогда имеем

или ,

(1)

где:  -искомая вектор-функция; t-независимая переменная; ;  , n - порядок   системы;  - координаты;  .

Также обозначим  - точное, и  - приближенное решение в узле .

Введем еще два необходимых понятия.

Определение 1. Метод сходится к точному решению в некоторой точке t , если   при  h®0, .

Метод сходится  на некотором интервале, если он сходится в любой точке этого интервала.

Определение 2. Метод имеет  р-й порядок точности, если существует такое число  р>0, для которого  при  h®0, где: h- шаг интегрирования; O-малая величина порядка .

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

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

Можно выделить два класса методов для решения задачи (1):

1) одношаговые методы (Рунге-Кутты);

2) многошаговые (m-шаговые) методы.

Сначала рассмотрим одношаговые методы.

2. Метод Эйлера (частный случай метода Рунге-Кутты)                

Расчетные формулы метода Эйлера можно получить различными способами, например:

-геометрический -  на основе построения касательной к искомой функции в начальной точке;

-на основе разложения искомой функции в ряд Тейлора;

-разностный способ, на основе аппроксимации производной разностным отношением;

-квадратурный способ, на основе формул прямоугольников (правых, левых, или на основе формулы трапеций)

Можно привести различные виды метода Эйлера: явный, неявный, уточненный, исправленный. Рассмотрим явный метод Эйлера.

Сначала возьмем одно уравнение

или ,

(2)

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

Уравнение (2) заменяется разностным уравнением

, i=0,1,2,….

Тогда в окончательной форме значения  можно определить по явной формуле

.

(3)

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

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

Приведем без вывода неявный метод Эйлера

.

(4)

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

В случае решения  нормальных систем дифференциальных уравнений (1) формулы явного метода Эйлера принимают вид:

.

(5)

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

Существуют различные подходы к получению формул метода Рунге-Кутты, рассмотрим один из них. Идея заключается в получении приближений к значениям  по формуле вида

,

(6)

где  - некоторая функция приближающая отрезок ряда Тейлора до p-го порядка и не содержащая частных производных функции  . Так, полагая в (6) , приходим к методу Эйлера, таким образом, метод Эйлера – частный случай методов Рунге-Кутты порядка p=1. Для построения методов Рунге-Кутты порядка, выше первого, функцию  берут многопараметрической, и подбирают ее параметры сравнением выражения (6) с многочленом Тейлора для функции  соответствующего порядка точности.

Метод Рунге-Кутты второго порядка точности

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

,

(7)

где  .

Метод (7) имеет второй порядок точности, т.е. .

Отличительная особенность методов Рунге-Кутта от метода (4) заключается в том, что значение правой части уравнения вычисляется не только в точках сетки, но и также в середине отрезков (промежуточных точках). Метод (7) иногда называют методом средней точки.

Приведем один из методов Рунге-Кутта третьего порядка точности

,

(8)

где  ; ;

 .

Метод Рунге-Кутта 4-го порядка точности

Рекуррентные формулы для одного уравнения имеют вид:

,

(9)

где:    

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

.

(10)

Можно использовать другой подход, требующий меньшее количество расчетов, позволяющий определять достаточно ли малым выбран шаг h для расчетов по методу Рунге-Кутты 4-го порядка точности: при каждом i=0,1,… вычисляют величины

.

(11)

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

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

Тема 2.5. Численное решение задач оптимизации( 6 часов)

Тип лекции: текущая

План:

1. Постановка задачи оптимизации

2. Поиск минимума функции одной переменной

3. Метод дихотомии

4. Метод золотого сечения

5. Минимизация функции многих переменных

6. Вопрос для самостоятельного изучения:

-Решение задач оптимизации с помощью инструментальных средств

1. Постановка задач оптимизации

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

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

На рис. проиллюстрирован график функции, у которого на отрезке [а; b] имеется несколько максимумов (три) и минимумов (два). Самый «высокий» из максимумов (достигаемый при х=а) оказался на краю отрезка, самый «низкий»

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

Если функция y= f (x) является на отрезке [а; b]  дифференцируемой, то для поиска ее максимумов и минимумов существуют простые приемы. Напомним их: для того чтобы точка x₀ была точкой внутреннего (по отношению к отрезку) экстремума, необходимо, чтобы она была корнем уравнения f (x) = 0. Если у функции существует вторая производная, то при f "(x₀) > 0 х₀ будет точкой минимума, а при f "(х₀) < 0 — максимума.

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

 Иллюстрация к экстремумам функции одной переменной

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

f '(x) = 0 называют косвенным методом. У той и другой групп методов есть варианты и применительно к функциям многих переменных.

2. Поиск минимума функции одной переменной

Рассмотрим задачу поиска минимума функции f (х), определенной на отрезке [а; b], способами, не связанными с решением уравнения f (х) = 0. При этом достаточно ограничиться поисками минимумов лишь во внутренних точках отрезка, поскольку вычисление значений функции на его концах задача тривиальная.

Все, сказанное об отделении корней уравнений, можно повторить об отделении минимумов. Эта задача не имеет формализованных, однозначно ведущих к успеху, решений. Мы сосредоточимся на поиске минимума, считая, что на данном отрезке он существует и единственен. Иначе говоря, будем считать, что функция f (х) является на отрезке [а; b] унимодальной, т.е. монотонно убывающей слева от точки минимума и монотонно возрастающей справа от нее.

Приведем также более строгое описание унимодальности. Непрерывная функция у=f(х) является унимодальной на отрезке [а; b], если:

Рис. К определению унимодальности функции у=f(х)

1) точка ξ локального минимума функции принадлежит отрезку [а; b];

2) для любых двух точек отрезка х₁ и х₂, взятых по одну сторону от точки минимума, точке х₁, более близкой к точке минимума, всегда соответствует меньшее значение функции, т.е. неравенство f (х₁) < f (х₂) справедливо как при ξ <х₁ <х₂ (рис. 7.2, а), так и при х₂<х₁ < ξ (рис. 7.2, б).

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

3. Метод дихотомии

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

На рис. проиллюстрирован первый шаг указанного метода. Искомый минимум находится в точке ξ. Разделим отрезок [а; b] пополам точкой с=(а + b)/2. Если (как это имеет место на рис. 7.3) точка минимума оказалось левее точки с, то следующий отрезок, подлежащий делению пополам, есть [а; с], иначе — [с; b].

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

Пусть точность, с которой мы хотим оценить значение с, есть ε. Будем вычислять не одно значение f (с), а два: f (с- ε/2) и f (с + ε /2). Учитывая предполагаемую унимодальность функции f(х) , ясно, что при f (с- ε/2) < f (с + ε /2) следующему делению пополам подле жит отрезок [а; с] (или, что практически то же самое, [а; с - ε /2]). Если же f (с - ε /2)> f (с + ε /2), то делению подлежит отрезок [с; b]. Итерационный вычислительный процесс продлится до тех пор, пока длина очередного отрезка не станет меньше ε. Наконец, нельзя исключить ситуацию, когда на очередном шаге f (с - ε /2)= f (с + ε /2), т.е. искомая точка, в которой функция f(х) имеет минимум, оказалась между с - ε /2 и с + ε /2; в этом случае результат решения задачи (с заданной точностью) есть с.

4. Метод золотого сечения

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

Золотое сечение — это такое пропорциональное деление отрезка на части, при котором весь отрезок относится к большей части, как сама большая часть относится к меньшей; другими слова ми, меньший отрезок относится к большему, как больший ко всему (рис. 7.5) β: γ= γ :α.

Из приведенною ранее соотношения получаем уравнение для определения γ (считая α заданным): γ ² = αβ, или γ ² = α (α - γ). Решение последнего уравнения:

Обратим внимание, что заданный отрезок [а; b] можно разделить на две части в соответствии с золотым сечением двумя способами: располагая меньший отрезок слева (см. рис. 7.5) или справа, т.е. на отрезке есть две точки золотого сечения.Считается, что понятие о золотом сечении ввел в научный обиход Пифагор, хотя следы его использования находят в строениях, сделанных  до жизни Пифагора,египетских пирамидах, храмах разных народов и т.д.

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

Вернемся к решению задачи о минимизации унимодальной на отрезке [а; b] функции f(х). Найдем обе точки золотого сечения: левую

и симметричную ей правую

Сравним значения f(х) в этих точках. Если окажется, что f(с) >f(d), то новый отрезок для поиска минимума есть [с; b]. если же f(c)<f(d), то новый отрезок [а; d] (см. рис. 7.6).

Допустим для определенности, что ситуация такова, как на рис. 7.6 слева, т.е. на втором шаге минимум ищется на отрезке [с; b]. Продолжим использовать тот же прием: выполним золотое сечение этого отрезка.

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

Следующее утверждение является причиной эффективности этого метода в решении задачи минимизации: одна из двух точек нового сечения — уже известная нам точка d. Действительно, найдем левую точку золотого сечения отрезка [с; b], для чего надо в формуле

заменить a на с:

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

 Блок-схема алгоритма поиска минимума унимодальной функции на отрезке [а; Ь] методом золотого сечения

5. Минимизация функции многих переменных

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

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

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

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

Рис.К вопросу о минимуме функции двух переменных

Важно, что эти линии можно получать не только проецированием сечений поверхности, как это изображено на рис. 7.8, а и вовсе не располагая трехмерным геометрическим образом. Для этого составляется уравнение f(x, у) = С и строятся в плоскости ху линии, соответствующие различным значениям С. Если линии расположены в соответствии с изменением С следующим образом (рис. 7.9): С₁ > С₂ > С₃ > С₄ > ... и если функция f(x, у) непрерывна, то очевидно, что ее локальный минимум достигается в некоторой точке, находящейся внутри области, ограниченной внутренней кривой.

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

Перечень источников:

1. Численные методы. Сборник задач: учеб. пособие для вузов/Ч-67

В. Ю. Гидаспов, И.Э.Иванов, Д. Л. Ревизников и др.; под ред.У. Г. Пирумова.

- М. : Дрофа, 2007.-144с.: ил.

2. Балахов Н.С., Жидков Н.П., Кобельков Г.М. «Численные методы» - М.:СПб.: Лаборатория базовых знаний. 2002.- 342 с.

3. Вержбицкий В.М. Основы численных методов: учебник для вузов. М.: Высшая школа, 2002. - 302 с.

4. Лапчик М.П., Рагулина М.И., Хеннер Е.К. Численные методы: учебное пособие для студентов вузов/.-М.: Издательский центр «Академия», 2004.- 362 с.

5. Вержбицкий В.М. Численные методы: учебник. для вузов. М.: ОНИКС 21 век, 2005. - 430 с.

6. Воробьева Г.Н., Данилова А.Н. Практикум по численным методам - М.: Высшая школа, 1979г. - 234 с.

7. Данилина Н.И,, Дубровская Н.С., Кваша О.П., Смирнов Г.Л. «Вычислительная математика: учебное пособие для техникумов»- М.: Высшая школа, 1985 - 345 с.