Вопрос 5
Итерационный процесс - последовательное приближение и проверка условия достижения искомого результата. В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса) . В противном случае произойдет зацикливание алгоритма. Этот процесс состоит в том, что для решения некоторой задачи и нахождения искомого значения определяемого параметра (например, корня нелинейного уравнения) строится
метод последовательных приближений. В результате многократного повторения этого процесса (или итераций) получаем последовательность значений x1, x2,…, xn,… Говорят, что эта последовательность сходится к точному решению x = a, если при неограниченном возрастании числа итераций предел этой последовательности существует и равен a: . В этом случае имеем сходящийся численный метод.
Вопрос 6
Последовательных приближении метод, метод когда каждое новое приближение вычисляют, исходя из предыдущего; начальное приближение выбирается в достаточной степени произвольно.Этот метод применяется для приближённого нахождения корней алгебраических и трансцендентных уравнений, для доказательства существования решения и приближённого нахождения решений дифференциальных, интегральных и интегро-дифференциальных уравнений
Вопрос 7
Решить уравнение - значит найти все его корни, то есть те значения x, которые обращают уравнение в тождество, или доказать, что корней нет. Решение уравнения состоит из двух этапов: 1) Отделение корней, то есть нахождение интервалов из области определения функции f (x), в каждом из которых содержится только один корень уравнения 2) Уточнение корней до заданной точности.
Вопрос 8
Отделение корней можно проводить графически и аналитически.Для того чтобы графически отделить корни уравнения,необходимо построить график функции . Абсциссы точек его пересечения с осью Ox являются действительными корнями уравнения. Аналитическое отделение корней основано на следующихтеоремах.Теорема 1. Если непрерывная функция принимает на концах отрезка значения разных знаков, т.е. , то на этом отрезке содержится по крайней мере один корень уравнения. Теорема 2. Если непрерывная на отрезке функция принимает на концах отрезка значения разных знаков, а производная сохраняет знак внутри отрезка , то внутри отрезка существует единственный корень уравнения f (x) = 0
Вопрос 9
Метод
хорд использует пропорциональное
деление интервала. Вычисляются значения
функции на концах отрезка, и строится
"хорда", соединяющая
точки (a,f(a)) и (b,f(b)). Точка
пересечения ее с осью абсцисс принимается
за очередное приближение к корню.
Анализируя знак f(z) в сопоставлении
со знаком f(x) на концах отрезка,
сужаем интервал до [a,z] или [z,b] и продолжаем
процесс построения хорд до тех пор, пока
разница между очередными приближениями
не окажется достаточно малой (в пределах
допустимой погрешности) 
Вопрос 10
Метод Бисекций.Согласно методу бисекций,найденый отрезок [a.b] делится пополам точкой с=(а+в)/2 и далее рассматриваются два отрезка а,с и с,в.Затем определяется в каком из полученных отрезков находится корень уравнения .Если у(а)*у(с)<0 то в дальнейшем ршении участвует отрезок (а,с) если у(с)*у(в) <0 то отрезок (с,в) и процесс деления повторяется.
|
Метод бисекции или метод деления отрезка пополам — простейший численный метод для решения нелинейных уравнений вида f(x)=0. Предполагается только непрерывность функции f(x). Поиск основывается на теореме о промежуточных значениях. если мы ищем ноль, то на концах отрезка функция должна быть противоположных знаков. Разделим отрезок пополам и возьмём ту из половинок, на концах которой функция по-прежнему принимает значения противоположных знаков. Если значение функции в серединной точке оказалось искомым нулём, то процесс завершается. Процедуру следует продолжать до достижения заданной точности. Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать ноль получившейся функции. |
|
11. Метод касательных. Метод Ньютона, алгоритм Ньютона (также известный как метод касательных) — это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Также метод Ньютона может быть использован для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства. |
|
12.Метод итераций. Метод простой итерации — один из простейших численных методов решения уравнений. Метод основан на принципе сжимающего отображения, который применительно к численным методам в общем виде также может называться методом простой итерации или методом последовательных приближений[1]. В частности, для систем линейных алгебраических уравнений существует аналогичный метод итерации. |
13 нет
14 §1. Изложение метода Рассмотрим систему нелинейных уравнений F(x) = 0, F(x), x ∈ R n , (1.1) и предположим, что существует вектор x¯ ∈ D ⊂ Rn , явля- ющийся решением системы (1.1). Будем считать, что F(x) = (f1(x), f2(x), . . . , fn(x))T , причём fi (·) ∈ C 1 (D) ∀i. Разложим F(x) в окрестности точки x¯: F(x) = F(x 0 ) + F 0 (x 0 )(x − x 0 ) + o(kx − x 0 k). Здесь F 0 (x) = ∂F(x) ∂x = ∂f1(x) ∂x1 , ∂f1(x) ∂x2 , . . . ∂f1(x) ∂xn ∂f2(x) ∂x1 , ∂f2(x) ∂x2 , . . . ∂f2(x) ∂xn . . . . . . . . . . . . ∂fn(x) ∂x1 , ∂fn(x) ∂x2 , . . . ∂fn(x) ∂xn называется матрицей Якоби, а её определитель – якобианом си- стемы (1.1). Исходное уравнение заменим следующим: F(x 0 ) + F 0 (x 0 )(x − x 0 ) = 0. Считая матрицу Якоби F 0 (x 0 ) неособой, раз- решим это уравнение относительно x: xˆ = x 0 − [F 0 (x)]−1 F(x 0 ). И вообще положим x k+1 = x k − [F 0 (x k )]−1 F(x k ). (1.2) При сделанных относительно F(·) предположениях имеет ме- сто сходимость последовательности {x k } к решению системы со скоростью геометрической прогрессии при условии, что начальное приближение x 0 выбрано из достаточно малой окрестности реше- ния x¯. При дополнительном предположении F(·) ∈ C 2 [a, b] имеет ме- сто квадратичная сходимость метода, т.е. kx k+1 − x¯k ≤ ωkx k − x¯k 2 . 7 Перейти к оглавлению на странице: 12 Сформулируем теорему. Теорема 1.1. Пусть в некоторой окрестности решения x¯ си- стемы (1.1) функции fi (·) ∈ C 2 [a, b] и якобиан системы отличен от нуля в этой окрестности. Тогда существует δ -окрестность точки x¯ такая, что при любом выборе начального приближения x 0 из этой окрестности последовательность {x k } не выходит из неё и имеет место квадратичная сходимость этой последова- тельности. Замечание 1.1. В качестве критерия окончания процесса итераций обычно берут условие: kx k+1 − x k k < ε. Замечание 1.2. Сложность метода Ньютона – в обращении мат- рицы Якоби. Вводя обозначение δxk = x k+1 − x k получаем для вычисления δxk СЛАУ ∂F(x k ) ∂x · δxk = −F(x k ), (1.3) откуда и находим искомую поправку δxk , а затем и следующее приближение x k+1 = x k + δx к решению x. ¯ Очевидно, что это значительно сокращает количество арифметических операций для построения очередного приближения. Замечание 1.3. Начиная с некоторого шага k0 решают стационар- ную СЛАУ ∂F(x k0 ) ∂x · δxk = −F(x k ). Данное видоизменение носит название модифицированный метод Ньютона. Замечание 1.4. (О выборе начального приближения). Пусть вектор-функция Φ(λ, x) такова, что Φ(1, x) = F(x), а система Φ(0, x) = 0 может быть решена. Тогда разбивая [0, 1] на N частей решают методом Ньютона набор из N систем Φ(i/N, x) = 0, i = 1, N, принимая для каждой следующей системы в качестве начального приближения решение предыдущей системы.
15
Класс уравнений, для которых можно получить точное решение, то есть, аналитическую функцию, удовлетворяющую заданному дифференциальному уравнению и всем дополнительным условиям (задача Коши), очень узок. Чаще всего дифференциальные уравнения решаются приближенно. С одним из методов – итерационным – мы познакомились при доказательстве теоремы существования и единственности.
1. Приближение
решения с помощью степенного ряда.
Представим, что мы должны решить задачу
Коши для дифференциального уравнения 
-го
порядка 
с
начальным условием 
.
Если функция 
в
правой части уравнения разлагается в
ряды по всем своим переменным, удобно
искать решение дифференциального
уравнения в окрестности точки 
в
виде ряда Тейлора по степеням 
.
Представим решение в виде 
.
Из начальных условий и свойств
коэффициентов ряда Тейлора следует,
что все коэффициенты разложения вплоть
до 
нам
известны:
остальные –
неизвестные – коэффициенты обозначаются
буквами 
и
определяются сравнением коэффициентов
при одинаковых степенях, находящихся
в обеих частях дифференциального
уравнения.
16. Метод Эйлера и
его модификации. Познакомимся с методом
Эйлера численного решения задачи Коши
для дифференциального уравнения первого
порядка 
.
Предположим, что мы должны решить задачу
на отрезке 
.
Разделим отрезок
на
равных
частей, равных 
.
Заменим на каждом отрезке 
, 
,
решение дифференциального уравнения
линейной функцией 
.
При этом имеем узловые значения решения: 
Мы здесь приравниваем отношение приращений функции и аргумента производной в точке, соответствующей началу отрезка разбиения:
.
Очевидно, что такое
приближение является тем менее точным,
чем дальше мы отойдем от точки 
.
Метод Эйлера является наиболее
примитивным. Здесь интегральная кривая
заменяется ломаной, состоящей из
прямолинейных отрезков. Возможны его
некоторые модификации, несколько
улучшающие точность. Например, если
брать постоянные значения в виде
.
Наиболее распространенным численным методом решения указанной задачи Коши является метод Рунге-Кутта.При решениидифференциального уравнения этим методом интегральная кривая заменяется ломаной, состоящей из кусков парабол. Метод Рунге-Кутта встроен в пакет программ MAXIMA.
17.Приближенное
решение дифференциальных уравнений
высших порядков сводятся к решению
систем уравнений первого порядка.
Например, требуется решить дифференциальное
уравнение 
на
отрезке [0,2] с шагом 0.1 при начальных
условиях 
.
Введем новую функцию 
.
Теперь уравнение запишется в виде
системы 
с начальными
условиями 
.
18. Графический
метод. Этим методом можно решать
дифференциальные уравнения первого
порядка вида 
.
Если нам необходимо построить интегральные
кривые, которые являются графиками
решений приведенного уравнения, в
какой-то части плоскости 
,
мы каждой точке
этой
области ставим в соответствие значение 
,
которое совпадает с тангенсом угла
наклона касательной к интегральной
кривой, проходящей через точку
.
Зная точку и направление движения по
кривой из этой точки, мы переходим к
близкой точке, в которой также определяем
направление движения,…. Так, двигаясь
от точки к точке, мы построим соответствующую
интегральную кривую, то есть, решим
задачу Коши
.
Реальное построение
решения таким методом было бы очень
сложным без применения компьютерной
техники. MAXIMA содержит программу построения
графических решений. Если мы
введем load(plotdf); plotdf(f(x,y),[y,c,d],[x,a,b]), на
экране появится прямоугольник 
,
в точках которого указаны направления
касательных к интегральным кривым,
проходящим через эти точки. Если щелкнуть
курсором по выбранной точке на плоскости,
компьютер нарисует интегральную кривую,
проходящую через соответствующую точку.
19
1 Численные методы решения задачи Коши для обыкновенных дифференциальных уравнений 1 Постановка задачи В области D = {a ≤ x ≤ b, |y i − y i 0 | ≤ bi} ∈ Rn+1 определена функция f ≡ f(x, y1 , . . . , yn ), (x, y) ∈ D. Необходимо найти решение dy dx = f(x, y) (1) удовлетворяющее начальному условию y(x0) = y0. (2) Используя метод последовательных приближений Пикара, можно получить точное решение y(x) задачи Коши (1),(2) как предел последовательности y0(x), y1(x), . . . , yk(x), . . . , (3) где yk(x) = y0(x) + Z x x0 f(x, yk−1(x)) dx, k = 1, 2 . . . . (4) Для сходимости этой последовательности необходимо выполнение условий: • f(x, y) непрерывна в D ; • f(x, y) удовлетворяет условию Липшица по аргументу y kf(x, yˆ) − f(x, y¯)k ≤ Lkyˆ − y¯k (5) для всех x ∈ [a, b] и всех компонент векторов yˆ и y¯ . При этих предположениях yk(x) равномерно сходится к точному решению задачи Коши, поэтому для достаточно больших k отклонение ky(x) − yk(x)k не превышает заданной величины. Таким образом, в качестве искомого решения можно взять yk(x) . Практическая реализация этого метода затруднена по причине того, что для сложной функции f(x, y) интеграл не берется в квадратурах и решение нельзя получить в аналитическом виде. Константа Липшица L играет важную роль в численных методах. Обсуждаемые ниже численнные методы известны как дискретные, т.е. такие методы, посредством которых вычисляется последовательность приближений yi ≈ y(xi) на множестве точек xi+1 = xi + hi , i = 0, 1, . . . , N − 1; xN = b, hi > 0− шаг сетки. В большинстве рассматриваемых методов будем считать hi = h, h = const > 0, i = 1, 2, . . . . Для облегчения изложения будем в дальнейшем рассматривать методы для скалярного случая (1) n = 1 и отдельно оговаривать их распространение на случай систем
20
ПОЛНАЯ ПРОБЛЕМА
ПОЛНАЯ ПРОБЛЕМА
собственных значений - задача вычисления всех (в отличие отчастичной проблемы).собственных значений квадратной матрицы, обычно действительной иликомплексной. Часто помимо собственных значений требуется еще и построение базиса из собственных иликорневых векторов матрицы.
Решение П. п. собственных значений матрицы Асводится к построению характеристич. многочлена j А этойматрицы и вычислению его корней, действительных или комплексных (последнее обусловливаетневозможность нахождения собственных значений конечным вычислительным процессом). Для каждогособственного значения l соответствующие собственные векторы могут быть определены из однороднойсистемы линейных уравнений ( А-lЕ) х=0 ( Е - единичная матрица). При вычислениях над полем комплексныхчисел достаточным условием существования базиса из собственных векторов является простота спектра, анеобходимое и достаточное условие состоит в том, чтобы алгебраич. кратность каждого собственногозначения l. (т. е. его кратность как корня характеристич. многочлена jA) совпадала с его геометрич.кратностью, под к-рой понимается дефект матрицы А-l Е. При необходимости вычисления корневых вектороввысоты, превосходящей единицу, приходится рассматривать однородные системы вида
Примерно по этой схеме строились и численные методы решения П. п. собственных значений,практиковавшиеся до кон. 1940-х гг. В 1930-х гг. были разработаны высокоэффективные (по количествуарифметич. операций) алгоритмы вычисления характеристич. многочлена матрицы по ее коэффициентам.Так, в методе Данилевского построение характеристич. многочлена матрицы порядка пвыполняется сзатратой ~n3 мультипликативных операций (см. [1], [2]).