Теория к работе 8. Итерационные методы решения линейных алгебраических уравнений
 Скачать 0.84 Mb.
|
|
Теоретические материалы к работе 8 Итерационные методы решения ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ уравнений Рассматриваемые темы:
3. Метод касательных (метод Ньютона) 1. Классификация методов решения алгебраических уравнений и систем линейных алгебраических уравнений Определение: линейное алгебраическое уравнение (ЛАУ)— это алгебраическое уравнение, у которого полная степень составляющих его многочленов равна 1 где x1… xn – неизвестные, a1…an , b – свободные коэффициенты. Все остальные виды уравнений можно отнести к нелинейным. Определение: система линейных алгебраических уравнений (СЛАУ) имеет следующий вид . . . и называется линейной. обозначения: aij – набор коэффициентов; xi – неизвестные; bi – свободные члены. aij индекс i обозначает строку индекс j обозначает столбец 1. Классификация методов решения алгебраических уравнений и систем линейных алгебраических уравнений Методы решений ЛАУ и СЛАУ Точные Итерационные (!) Точные методы решения уравнений позволяют найти решение с нулевой погрешностью. Это класс идеально точных решений. (!) Итерационные методы - приближенные методы решения ЛАУ и СЛАУ, которые позволяет получить значения корня ЛАУ или корней СЛАУ с изначально заданной точностью или погрешностью. 1. Классификация методов решения алгебраических уравнений и систем линейных алгебраических уравнений Примечание: данная классификация имеет место не только для линейных уравнений, но и для нелинейных алгебраических уравнений. Методы решений алгебраических уравнений Точные Итерационные Пример: дано АУ: Точное решение уравнения имеет 2 корня: x1 = 1, x2= –2 Итерационное решение имеет 2 корня: x1 = 1 ± ε, x2= –2 ± ε погрешность 1. Классификация методов решения алгебраических уравнений и систем линейных алгебраических уравнений Преимущества и недостатки точных и итерационных методов решения линейных и нелинейных алгебраических уравнений:
(!!!) Решение таких уравнений можно найти только итерационным методом, т.е. решение будет иметь некоторую погрешность, которую можно проконтролировать. 1. Классификация методов решения алгебраических уравнений и систем линейных алгебраических уравнений 1. Классификация методов решения алгебраических уравнений и систем линейных алгебраических уравнений Наиболее распространенными итерационными методами решений алгебраических уравнений являются:
2. Метод половинного деления (метод дихотомии) Ограничение метода – позволяет найти корни уравнения на заданном отрезке только в том случае, если этот корень единственный на заданном отрезке. Пример. Дано нелинейное уравнение: На заданном промежутке уравнение имеет 2 корня Корень 1 Корень 2 Метод половинного деления не позволяет найти сразу два и более корней уравнения. Он позволяет найти только 1 корень уравнения. В связи с этим процесс нахождения корней уравнения методом дихотомии необходимо разбить на два этапа: 1) отделение корней 2) уточнение корней. Определение: корнем уравнения f(x) = 0 называется такое значение аргумента x, подстановка которого в уравнение обращает его в тождество. Отделить корень уравнения f(x) = 0 – значит найти такой конечный промежуток [a, b] (отрезок изоляции), внутри которого имеется единственный корень данного уравнения. Отделение корней можно осуществить аналитически или графически. Но графически намного проще. 2. Метод половинного деления (метод дихотомии) 2. Метод половинного деления (метод дихотомии) Отделение корней В качестве примера рассмотрим уравнение: exp(x)-ln(x+6.1)=0 на отрезке [-6, 1], включая концы данного промежутка. Отделение корней осуществляется при выполнении следующей последовательности действий: 1) Построение графика данной функции в каком-либо графическом редакторе, (Origin, Excel,…). В качестве примера рассмотрим уравнение: x2+x–100=0 на отрезке [-15, 15], включая концы данного промежутка. 2. Метод половинного деления (метод дихотомии) Отделение корней 2) На построенном графике определим координаты по оси ОХ, являющиеся пересечением с графиком функции. Они отмечены кружками на рисунке Корень 1 Корень 2 2. Метод половинного деления (метод дихотомии) Отделение корней 2) очевидно, что на данном отрезке уравнение имеет два корня. Первый корень находится на отрезке (-6, -2), второй – на отрезке (0, 1). Примечание: концы отрезка не являются жестко закрепленными. Главное, чтобы внутри отрезка существовал корень уравнения и был единственным. Корень 1 Корень 2 2. Метод половинного деления (метод дихотомии) Уточнение корней. Поиск приближенного значения корня с точностью до заданного достаточно малого числа ε > 0 называется уточнением этого корня. Пусть функция f(x) непрерывна на [a, b] и имеет единственный корень на данном отрезке, т.е. этап отделения корней уже завершен. Алгоритм поиска корня: 1) Разделим [a; b] пополам точкой c1 = (a+b)/2 и вычислим значение функции в точке f(c1). 2) Если f(c1) = 0, то корень на данном отрезке является найденным. 2. Метод половинного деления (метод дихотомии) Уточнение корней. Если же f(c1) ≠ 0, то выполняется следующая последовательность действий. Далее рассмотрим два случая. Случай 1) Пусть f(a)<0, а f(b)>0. Это значит, что функция возрастает. Проводится анализ знака f(c1). Если f(c1) > 0, то проводим корректировку отрезка, на котором проводится поиск решения: [a1;b1], где a1=a, b1 = c1 . Если f(c1) < 0, то поиск решения будет осуществляться на отрезке: [a1;b1], a1 = c1, b1 = b. корень корень 2. Метод половинного деления (метод дихотомии) Уточнение корней. Случай 2) Пусть f(a)>0, а f(b)<0. Это значит, что функция убывает. Проводится анализ знака f(c1). Если f(c1) > 0, то проводим корректировку отрезка, на котором проводится поиск решения: [a1;b1], где a1=c1, b1 = b . Если f(c1) < 0, то поиск решения будет осуществляться на отрезке: [a1;b1], a1 = a, b1 = c1. а b c1 f(c1) < 0 новая правая граница b а c1 f(c1) > 0 новая левая граница 2. Метод половинного деления (метод дихотомии) Уточнение корней. 3) Для того, чтобы найти приближенное значение корня с точностью до ε > 0, необходимо остановить процесс половинного деления на таком шаге n, на котором отрезок [an; bn] будет иметь длину bn - an ≤ ε и вычислить x = (an + bn)/2, что и будет являться корнем уравнения. Если условие bn - an ≤ ε не удовлетворено, что возвращаемся к пункту (а) 2. Метод половинного деления (метод дихотомии) Алгоритм нахождения корней можно описать в виде блок-схемы. Рассматривается только случай, когда f(a)<0, а f(b)>0 2. Метод половинного деления (метод дихотомии) Пример: найти корни уравнения exp(x)-ln(x+6.1)=0 на отрезке [-6, 1]. Шаг 1. Отделение корней. Ранее было показано, что на данном отрезке данное уравнение имеет два корня . Первый – на отрезке [-6, -2], второй – на отрезке [0, 1]. Корень 1 Корень 2 2. Метод половинного деления (метод дихотомии) Шаг 2. Определяем самостоятельно точность или погрешность итерационных вычислений: ε = 0.001. Шаг. 3. Ищем корень на отрезке [-6, -2]. Начинаем заполнение таблицы Значения функции exp(x)-ln(x+6.1) в точках a, b и с c=(a+b)/2 2. Метод половинного деления (метод дихотомии) Запись условий ЕСЛИ =ЕСЛИ(E2<0; A2;B2) =ЕСЛИ(E2>0; C2;B2) Если значение функции в точке с больше 0, то происходит смещение правой границы: b = c Если значение функции в точке с меньше 0, то происходит смещение левой границы: a = c Синтаксис оператора ЕСЛИ : =ЕСЛИ (условие; если условие выполнено, то ячейке присваивается значение, заложенное в данной ячейке; если условие не выполнено, то ячейке присваивается значение, заложенное в данной ячейке; ) 2. Метод половинного деления (метод дихотомии) Растягиваем таблицу 2. Метод половинного деления (метод дихотомии) корень ε=b-a < 0.001 2. Метод половинного деления (метод дихотомии) Количество итерационных шагов ε Закономерность – погрешность уменьшается с увеличением количества итерационных шагов Ищем корень на отрезке [0, 1]. 2. Метод половинного деления (метод дихотомии) Ответ: x1 = -5.094±0.0009; x2 = 0.646±0.0009 3. Метод касательных (метод Ньютона) Ограничение метода – позволяет найти корни уравнения на заданном отрезке только в том случае, если этот корень единственный на заданном отрезке. Метод касательных называется также методом Ньютона и относится к методам последовательных приближений. Данный метод является методом уточнения корней, т.е. применяется после операции отделения корней. Условия применения метода касательных: Пусть дано уравнение f(x) = 0 и на отрезке [a; b] а) находится единственный корень x, причем значения функции на концах отрезка f(a) и f(b) имеют разные знаки б) функция имеет непрерывные производные первого и второго порядков с отличными от нуля и сохраняющими постоянный знак значениями при всех x, принадлежащих отрезку [a; b]. 3. Метод касательных (метод Ньютона) Иными словами, даже если на отрезке [a; b] уравнение имеет один корень, метод касательных неприменим, поскольку график имеет точку перегиба, в которой производная равна 0. 3. Метод касательных (метод Ньютона) Проведем касательную к кривой y = f(x) в точке A(a; f(a)) до пересечения с осью OX. Из курса аналитической геометрии известно, что прямая с известным угловым коэффициентом k и проходящая через данную точку (x0; y0), описывается уравнением: 3. Метод касательных (метод Ньютона) В нашем случае это можно записать в виде: где f ’(a) – угловой коэффициент, характеризующий наклон касательной. Полагая, что y=0 в точке x=x1, уравнение (*) записывается в виде: (*) где f‘(a) ≠ 0. Полученное значение x1 – это первое приближение к корню. 3. Метод касательных (метод Ньютона) Проведя касательную через точку A1(x1; f(x1)) и найдя точку ее пересечения с осью OX, получим x2 – второе приближение к корню. Аналогично определяются последующие приближения: Это рабочая формула для нахождения корня уравнения методом касательных 3. Метод касательных (метод Ньютона) Пример: методом касательных найти корни уравнения exp(x)-ln(x+6.1)=0 на отрезке [-6, 0]. Шаг 1. Отделение корней. Построим график зависимости. В промежутке от [–6; 0] находится единственный корень. Корень 1 Корень 2 3. Метод касательных (метод Ньютона) На промежутке [-6, 0] находится точка перегиба, в которой производная равна 0.
Корень 1 Корень 2 перегиб Результат: отрезок нахождения корня следующий: [-6, -3]. 3. Метод касательных (метод Ньютона) Шаг 2. Найдем первую производную: Шаг 3. Результаты вычислений по формуле записываем в виде таблицы. Ищем значение x, при котором f(x) < ε. Пусть ε = 0.0001.
корень ε=0,00000105 3. Метод касательных (метод Ньютона) Сопоставление метода половинного деления и метода касательных погрешность требуемая точность Плюсы и минусы методов:
3. Метод касательных (метод Ньютона) Сопоставление метода половинного деления и метода касательных Спасибо за внимание |