Инновационный Евразийский Университет Кафедра «Математика» Слайд-лекции по дисциплине «Численные методы» для студентов специальности 050109 Математика. - презентация

1 Инновационный Евразийский Университет Кафедра «Математика» Слайд-лекции по дисциплине «Численные методы» для студентов специальности Математика Разработали: ст. преп. Сарбасова Н.Д., преп. Абылова Г.Ж.

2 Лекция 1. Решение нелинейных уравнений с одним неизвестным Содержание 1. Постановка задачи. 2. Отделение корня. 3. Уточнение корня. Метод деления отрезка пополам.

3 1. Постановка задачи Пусть f(х) = 0, где f(х) непрерывная функция. Нелинейные уравнения делятся: на алгебраические уравнения (f(х) алгебраические функции); трансцендентные уравнения (тригонометрические, показательные, логарифмические и др.).

4 Методы решений нелинейных уравнений делят на: прямые (когда корни получаются в виде конечной формулы); итерационные (методы последовательных приближений).

5 Три этапа поиска корня: 1) выбор отрезка [а, b], на котором имеется корень: если f (а) f (в) < 0, то существует с [a,b] и f(c) = 0 (это отделение корня); 2) выяснение того, что корень единственный: (при f '(х) > 0 монотонно возрастает, при f (х) < 0 монотонно убывает); 3) построение процесса, позволяющего сузить границы выделенного отрезка, то есть позволяющего найти приближенные значения корня с любой заданной точностью (это уточнение корня).

6 2. Отделение корня Рассмотрим на примере: x 3 – x – 1 = 0; Область определения функций разобьётся на три интервала: (–, –1/ ], (–1/, 1/ ), [1/, + ). Третий интервал содержит корни. Сузив интервал, получаем, что на интервале [1, 2] есть корень, и единственный. Отделение корня можно производить и графически.

7 Для этого уравнение f (х) = 0 сводят к уравнению: φ 1 (x) = φ 2 (x). Абсцисса точки их пересечения есть корень. Если рассматривать пример уравнения cos(x)=x 2, то получим график, приведенный на рис.1. Данное уравнение имеет два корня: на отрезке [–π/2, 0] и [0, π/2].

8 Рис. 1 Графическое отделение корня уравнения cos x = x 2

9 Для отделения корня можно активно использовать компьютер. Рис.2 - Блок-схема алгоритма отделения корней

10 3. Уточнение корня. Метод деления отрезка пополам Четыре метода уточнения корня: метод деления отрезка пополам, метод касательных метод простой итерации. метод хорд

11 Пусть на интервале [a,b] расположен один корень. Метод деления отрезка пополам заключается в следующем. Имеем: Определяем половину отрезка и вычисляем. Проверяем следующие условия: Если, то c – корень. Здесь - заданная точность. Если, то корень лежит в интервале. Если, то корень лежит на отрезке.

12 Через n итераций интервал будет равен Если выполняется условие то процесс поиска заканчивается и корень уравнения будет

13 Графически метод половинного деления выглядит следующим образом Рис. 3 – Графический метод

14 Рис. 4 Блок-схема метода деления отрезка пополам

15 Лекция 2. Уточнение корня нелинейного уравнения. Содержание 1. Метод Ньютона (метод касательных) 2. Метод итераций (простых) 3. Метод хорд

16 1. 1.Метод Ньютона (метод касательных) В методе касательных проводят касательную к кривой y = F(x) в одной из точек a или b отрезка, где имеется корень. Затем находят точку пересечения касательной с осью OX Рис. 5 Метод касательных

17 Рассмотрим полученный треугольник Aax. Для него: Учитывая, что F' (a) = tg(π – α)= –tg(α). и обобщив эти формулу, можем записать: Процесс следует продолжать, пока не будет достигнута требуемая точность. Пока не станет |F(x n ) | < ε (заданная точность).

18 Достоинство метода быстрая сходимость. Если выполняется условие: F''(х) (вторая производная) сохраняет знак и при этом F(x) и F''(х) имеют одинаковый знак, то процесс сходится так, что на каждой итерации число верных значащих цифр удваивается. Недостаток на каждой итерации велик объём вычислений (нужно, в частности, знать выражения для производной и так далее).

19 Рис. 6 Блок-схема метода Ньютона

20 2. Метод итераций (простых) Состоит в замене исходного уравнения f(x) = 0 эквивалентным ему уравнением x = (x) и построением последовательности x n+1 = (x n ), которая при n сходится к точному решению. Условием сходимости этого процесса является: | '(x)| < 1.

21 В качестве x 0 берут обычно один из концов отрезка [а, b]; если окажется, что '(x) < 0, то может оказаться, что x 1 будет вне отрезка. Это значит, что искомый корень ближе ко второму концу отрезка и именно его следует взять в качестве начального приближения. Рис. 7 Графическая интерпретация метода итераций (случай (x) убывает)

22 3. Метод хорд Рассмотрим более быстрый способ нахождения корня на интервале [a,b], в предположении, что Рис.8а Рис. 8б

23 Рассмотрим рис.8а. Проведем через точки А и В хорду. Уравнение хорды В точке, в результате получим первое приближение корня. (1) Проверяем условия а) б)

24 Если выполняется условие (а), то в формуле (1) заменяя точку а на х 1,, получим Окончательная формула для n-го приближения: Здесь подвижен конец а, то есть Аналогичная ситуация на рис 9а. Рассмотрим случай, когда неподвижен конец а.

25 Рис.9а Рис.9б

26 На рис 8б, 9б выполняется Затем вводим (в формуле (1) точку b заменяем на x 1 ), получим Продолжая процесс, придем к формуле Выполняется до тех пор, пока - корень уравнения.

27 Рис. 10 На рис. 10 меняет знак, поэтому подвижными будут оба конца.

28 Теорема. Пусть задана непрерывная: дважды дифференцируемая функция на и пусть а и сохраняют свои знаки на (см. рис 8а, 8б и рис 9а, 9б). Тогда итерационный процесс метода хорд сходится к корню с любой наперед заданной точностью.

29 Лекция 3. Решение систем линейных алгебраических уравнений. Содержание 1. Постановка задачи. Правило Крамера. 2. Метод обратной матрицы. 3. Метод Гаусса. 4. Итерационный метод Гаусса- Зейделя.

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

31 Постановка задачи. Пусть дана система линейных алгебраических уравнений а 11 x 1 + a 12 x 2 + … + a 1n x n = b 1 а 21 x 1 + a 22 x 2 + … + a 2n x n = b 2 …………………………………… а n1 x 1 + a n2 x 2 + … + a nn x n = b n

32 Используя понятия матрицы: и вектор столбца: систему уравнений можно переписать в виде: AX = B.

33 Правило Крамера состоит в вычислении главного определителя матрицы А: и побочных определителей: И тогда вычисление корней: x 1 = D 1 /D, x 2 = D 2 /D, … x n = D n /D. Число требуемых для вычисления определителей операций: N n(n! + 1).

34 2. Метод обратной матрицы Отталкиваясь от АХ = В, умножим обе части на обратную матрицу A -1 : A -1 А Х = A -1 В или Х = A -1 В. Таким образом, решение системы сводится к вычислению A -1, но её вычисление также трудоемко.

35 3. Метод Гаусса Рассмотрим на примере системы трех уравнений: а 11 x 1 + a 12 x 2 + a 13 x 3 = b 1 а 21 x 1 + a 22 x 2 + a 23 x 3 = b 2 а 31 x 1 + a 32 x 2 + a 33 x 3 = b 3 Прямой ход метода Гаусса состоит в следующем: Умножим первое уравнение на – a 21 /a 11 и сложим со вторым:

36 Если обозначить первую скобку за a 22, а вторую за a 23 и полученную правую часть за b 2, то получим: Аналогично: умножим первое уравнение на –a 31 /a 11, сложим с третьим уравнением и обозначим полученное уравнение так:

37 a 32 x 2 + a 33 x 3 = b 3. Обобщенная формула для «штриховых» коэффициентов. Исключим теперь x 2 из 3-го уравнения. Таким образом, система сведется к виду:

38 Для «дважды штриховых» коэффициентов общие формулы имеют вид: Обратный ход метода Гаусса состоит в следующем: Находим x 3 из 3-го уравнения: x 3 = b' 3 /a' 33 Потом находим x 2 = (b 2 – a 23 x 3 )/a 22, x 1 = (b 1 – a 12 x 2 – a 13 x 3 )/a 11.

39 Аналогично строится процесс метода Гаусса для системы из N уравнений. Обобщим формулы «штриховых» коэффициентов. Пример. Методом Гаусса решить систему:

40 4. Итерационный метод ГауссаЗейделя Рассмотрим метод ГауссаЗейделя (на примере трех уравнений) Выразим x 1, x 2 и x 3 соответственно из 1- го, 2-го и 3-го уравнений:

41 Зададим начальные (нулевые) приближения для неизвестных: И подставим их в эти соотношения, в результате последовательно получим первые приближения: Используя их, также найдем вторые приближения и так далее.

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

43 Лекция 4. Численное интегрирование. Содержание 1. 1.Метод прямоугольников Метод трапеций Метод Симпсона.

44 1. Метод прямоугольников. Вычислить определенный интеграл пользуясь формулой НьютонаЛейбница F (b) – F (а) иногда оказывается невозможным. В этом случае прибегают к приближенным численным методам вычисления определенных интегралов. Метод прямоугольников основан на определении интеграла:

45 где исходный отрезок [a, b] с помощью точек х 0 = а, х 1, х 2, …х h-1, х h = b разбит на n элементарных подотрезков [х i-1, х i ], i [х i-1, х i ]. Если обозначить f(x i ) = y i, то формула прямоугольников примет вид: где h = (b–a)/n, n число разбиений [a, b]. геометрическая интерпретация определенного интеграла

46 есть площадь так называемой криволинейной трапеции, Рис. 11 Криволинейная трапеция, ограниченная кривой y = f(x). Геометрическая интерпретация формулы прямоугольников приведена на рис. 12.

47 Рис. 12 Иллюстрация метода прямоугольников для различного числа разбиений: а для N = 12; б для N = 6 С ростом n (числа разбиений) результат будет точнее и точнее.

48 Рис. 13 Блок-схема метода прямоугольников

49 Ошибка формулы прямоугольников: где 4 наибольшее значение четвертой производной на отрезке [a, b]. Пример. Для заданного отрезка [a,b] с указанным числом разбиений N найти площадь под кривой (Заметим, что при а = 0 и b = 1 получится площадь четверти круга единичного радиуса см. рис. 14.)

50 Рис. 14 Иллюстрация метода прямоугольников на примере четверти круга

51 Программа на языке Паскаль, реализующую метод прямоугольников на этом примере : program pr4_1; var a, b, x, h, s:real; i, n:integer; function f(x:real):real; begin f:=sqrt(1-x*x); end; begin write('введи a,b,n '); read(a,b,n); h:=(b-a)/n; x:=a; s:=0; for i:=1 to n do begin s:=s+f(x); x:=x+h end; s:=s*h; writeln; write('площадь=',s,' число разбиений=',n); end.

52 2. Метод трапеций Рассматривая будем интерполировать подынтегральную функцию f(x) полиномом Лагранжа первой степени (линейной функцией): его узлы x 0 = a, x 1 = a+h; h = (b–a)/n, y 0 = f(x 0 ), y 1 = f(x 1 ). Тогда

53

54 Значит интеграл по всему отрезку [a, b]: Рис. 15 Графическая иллюстрация метода трапеций для N = 3.

55 Ошибка метода трапеций: где 2 наибольшее значение второй производной подынтегральной функции на отрезке [a, b], т.е. ошибка примерно вдвое меньше, чем у метода прямоугольников.

56 Рис. 16 Блок-схема алгоритма метода трапеций

57 3. Метод Симпсона Если подынтегральную функцию f(x) проинтерполировать полиномом Лагранжа 2-ой степени (на отрезке [x 0, x 2 ]): где x 1 = x 0 +h, x 2 = x 0 +2h, h = (b–a)/n, x 0 = a, y 0 = f(x 0 ), y 1 = f(x 1 ), y 2 = f(x 2 ) Рассмотрим отдельно первый интеграл:

58 Аналогично, А интеграл по всему отрезку: Это и есть формула Симпсона.

59 Ошибка её: h 4 (b–a) 4 /180, где 4 наибольшее значение модуля четвертой производной функции f(x) на отрезке (a, b). Геометрический смысл формулы Симпсона: площадь над кривой вычисляется как сумма площадей под участками парабол, то есть явно будет точнее (гибче), чем предыдущие методы.

60 Лекция 5. Численное решение дифференциальных уравнений Содержание 1. 1.Постановка задачи Метод Эйлера Метод Рунге-Кутты.

61 1. Постановка задачи Будем рассматривать задачу Коши: Найти функцию y(x), удовлетворяющую уравнению y' = f(x, y) и принимающую при x = x 0 заданное значение y 0. Решение нужно получать для x > x 0. Например, уравнение: Z'' = (Z', Z, x) сводится к системе:

62 Решение дифференциальных уравнений ищется не в виде аналитической функции, а в виде набора значений (x i, y i ), т.е. значений искомой функции в некоторых выбранных точках x i. x 1 = x 9 + h; x 2 = x 1 + h; ……………. Их называют узлами, а значения y i, соответствующие этим x i, называют сеткой функции y.

63 2. Метод Эйлера Если этот интеграл приближенно вычислить по формуле прямоугольников, взяв левую границу, то т.е. погрешность имеет порядок h 2. Учитывая, что y = f(x,y): Стоит задача вычисления y в некоторой последующей точке x 0 +h

64 или, для любой последующей точки x k+1 = x k +h, k = 0,1,… Это и есть формула метода Эйлера. Ее погрешность имеет порядок малости h 2. Таким образом, итоговая формула метода Эйлера может быть записана в виде: Если функцию y(x) разложить в ряд Тейлора в точке x k и ограничиться двумя членами, то получим:

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

66 3. Метод Рунге-Кутты В общем случае методы Рунге-Кутты имеют следующую структуру: где (1) s - число стадий (этапов), - значение коэффициентов схемы Рунге-Кутты, вычисленные на основе правой части уравнения,

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

68 Наибольшее распространение в вычислительной практике нашел метод РунгеКутты четвертого порядка: где (3)

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

70 Прямая АЕ, проходящая через точку и определяющая величину, имеет угловой коэффициент. Этот коэффициент рассчитывается по угловым коэффициентам касательных в точках A,B,C,D, проведенным к проходящим через эти точки интегральным кривым (штриховые линии). При этом коэффициент рассчитывается в точке А, коэффициент - в точке С, коэффициент - в точке В, а коэффициент - в точке D.

71 Рис. 17 – Геометрическая интерпретация метода Рунге-Кутты

72 Соотношения модифицированного метода Эйлера можно записать в форме схемы РунгеКутты: Эта схема второго порядка. Коэффициенты семейства методов РунгеКутты (1),(2) удобно записывать в виде табл. 1, табл. 2 соответствует классическому методу Рунге Кутты четвертого порядка (3), а в табл. 3 приведены коэффициенты другого метода четвертого порядка (правило ).

73 Табл. 1 Табл. 2 0 …………… … … … 0 1/ /62/6 1/6

74 Табл. 3 Таблица 4 соответствует методу Рунге Кутты второго порядка, Табл /3 2/3- 1/ /83/8 1/8 0 1/2 01

75 Контрольные вопросы 1. 1.Метод Гаусса решения СЛАУ. Условия применимости метода Правило Крамера решения СЛАУ Вычисление определителей и обращение матриц Метод простой итерации решения СЛАУ. Метод Зейделя Метод Ньютона и его модификации Метод простой итерации решения нелинейных уравнений Метод хорд и половинного деления Основные методы численного решения дифференциальных уравнений Недостаток метода Эйлера решения дифференциальных уравнений Ошибки методов трапеций и Симпсона.

76 Литература 1. 1.Бахвалов Н.С., Лапин А.В., Чижонков Е.В. Численные методы в задачах и упражнениях. – М., Воробьёва Г. Н., Данилова А.Н. Практикум по численным методам. - М.: Наука, Бахвалов Н. С., Жидков Н.П., Кобельков Г.М. Численные методы. - М.: Наука, Волков Е.А. Численные методы. - М.: Наука, Дьяченко В.Ф. Основные понятия вычислительной математики. - М.: Наука, Крылов В.И., Бобков В.В., Монастырский П.И. Вычислительные методы. В 2-х т. - М.: Наука, Самарский А.А. Введение в численные методы. - М.: Наука, Турчак Л.И. Основы численных методов. - М.: Наука, 1987.