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

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

  1. Mister Norm Ответить

    Макеты страниц

    2. Приближенное решение уравнений.

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

    Рис. 70
    заменяют график функции на отрезке хордой, соединяющей точки Уравнение этой хорды имеет вид:

    Она пересекает ось абсцисс в такой точке, где Полагая в равенстве находим, что

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

    Далее находим следующее приближение к корню:

    В общем случае можно записать:

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

    Рис. 71

    Рис. 72
    точка обозначается обычно через и называется начальным при 6 лишением.
    Предположим для определенности, что Тогда касательную надо проводить в точке т. е. начальное приближение Уравнение этой касательной имеет вид:

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

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

    Она сходится к корню I уравнения Вычисления прекращают, когда с заданной степенью точности совпадают значения
    Пример 6. Найдем действительный корень уравнения с точностью до методом хорд; б) методом касательных.
    Решение. Имеем:

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

    Так как
    Воспользовавшись формулой (11), находим второе приближение:

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

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

    Второе приближение:

    Третье приближение:

    Нужная точность достигнута уже на третьем шаге. Здесь сходимость процесса более быстрая, чем по методу хорд.

    Вопросы для самопроверки

    1. Опишите процесс решения уравнения методом хорд. Дайте геометрическое истолкование.
    2. Опишите процесс решения уравнения методом касательных. Дайте геометрическое истолкование. Каким условиям должна удовлетворять функция , чтобы можно было применить метод касательных?

    Упражнения

    (см. скан)

  2. MaFro Ответить

    (*)
    Пусть и
    (А) где
    Геометрически эти требования значат, что график должен быть монотонно возрастающим или убывающим в промежутке и притом должен располагаться более «полого» чем биссектриса 1-го координатного угла (если возрастает) и более «полого» чем если убывает.
    Приводя к виду (*) мы преобразуем тождество к виду т.е. корнем

    будет абсцисса точки , пересечения графика с
    Приведение к виду (*) можно выполнить различными способами. Например: : и т.д. Однако нужны только те преобразования, при которых выполняется (А). Подходящий вид находится методом проб. Так для для корня в промежутке вид является неподходящим, т.к. а вид – не удовлетворяет (А), т.к. для
    Если условие (А) соблюдается, то метод итераций позволяет вычислить корень с любой точностью. В качестве начального приближения можно выбрать любой из
    Метод итераций заключается в следующем:
    (*)
    Теорема. Если знакопостоянна на и по абсолютной величине строго меньше 1, т.е. где то последовательность (*) при имеет своим пределом точный корень , где
    Доказательство. Пусть окрестность симметрична относительно (Этого всегда можно достинуть, зная ). Обозначим её через Составим разности между членами и числом и преобразуем их по формуле Лагранжа, учитывая, что
    где
    Т.к. т.е. причём ближе к чем Далее

    т.е. ещё ближе к чем Продолжая этот процесс получим

    Теперь заметим, что т.к. все Поэтому

    или

    Рассмотрим теперь
    т.к.
    Ч.Т.Д.

    Можно также доказать, что монотонно при и колеблется около при
    Абсолютная погрешность го приближения оценивается неравенством:
    где
    Действительно

    ­

    но

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

  3. Mast Ответить

    Реферат по курсу численных методов выполнил студент группы РЭ–01-1
    Днепропетровский Национальный Университет
    Радиофизический факультет
    Кафедра физики СВЧ
    Днепропетровск 2002
    1. Численное решение уравнений с одним неизвестным
    В данной работе рассматриваются метода приближённого вычисления действительных корней алгебраического или трансцендентного уравнения
    f(x)=0 (1.1)
    на заданном отрезке [a, b].
    Уравнение называется алгебраическим, если заданная функция есть полином n-ой степени:
    f(x) = P(x) = a0
    xn
    + a1
    xn- 1
    + … + an
    -1
    x + an
    = 0, a0
    ¹ 0
    Требование a0
    ¹ 0 обязательно, так как при невыполнении этого условия данное уравнение будет на порядок ниже.
    Всякое уравнение (1.1) называется трансцендентным, если в нём невозможно явным образом найти неизвестное, а можно лишь приближённо.
    Однако в число алгебраических уравнений можно также включить те уравнения, которое после некоторых преобразований, можно привести к алгебраическому.
    Те методы, которые здесь рассматриваются, применимы, как к алгебраическим уравнениям, так и к трансцендентным.
    Корнем уравнения (1.1) называется такое число x, где f(x)=0.
    При определении приближённых корней уравнения (1.1) необходимо решить две задачи:
    отделение корней, т. е. определение достаточно малых промежутков, в каждом из которых заключён один и только один корень уравнения (простой и кратный);
    уточнение корней с заданной точностью (верным числом знаков до или после запятой);
    Первую задачу можно решить, разбив данный промежуток на достаточно большое количество промежутков, где бы уравнение имело ровно один корень: на концах промежутков имело значения разных знаков. Там где данное условие не выполняется, те промежутки откинуть.
    Вторая задача решается непосредственно в методах рассмотренных ниже.
    При графическом отделении корней уравнения (1.1) нужно последнее преобразовать к виду:
    j1
    (x)=j2
    (x) (2.1)
    и построить графики функций y1
    =j1
    (x), y2
    =j2
    (x).
    Действительно, корнями уравнения (1.1)
    f(x) = j1
    (x) – j2
    (x) = 0
    являются абсциссы точек пересечения этих графиков (и только они).
    Из всех способов, какими можно уравнение (1.1) преобразовать к виду (2.1) выбираем тот, который обеспечивает наиболее простое построение графиков y1
    =j1
    (x) и y2
    =j2
    (x). В частности можно взять j2
    (x) = 0 и тогда придём к построению графика функции (1.1), точки пересечения которого с прямой y2
    =j2
    (x)=0, т. е. с осью абсцисс, и есть искомые корни уравнения (1.0).
    Условия, наложенные на функцию f(x) на отрезке [a, b].
    Будем предполагать, что функция f(x) непрерывна на отрезке [a, b] (для метода хорд можно потребовать на интервале) и имеет на этом интервале первую и вторую производные, причём обе они знакопостоянны (в частности отличны от нуля). Будем также предполагать, что функция f(x) принимает на концах отрезка значения разного знака. В силу знакопостоянства первой производной функция f(x) строго монотонна, поэтому при сделанных предположениях уравнение (1.1) имеет в точности один корень на интервале (a, b).
    2. Метод дихотомии
    Этот метод ещё называется методом вилки.
    Нам необходимо найти корень уравнения (1.1) на отрезке [a, b]. Рассмотрим отрезок [x0
    , x1
    ]: [x0
    , x1
    ]I[a, b]. Пусть мы нашли такие точки х0
    , х1
    , что f (х0
    ) f(х1
    ) ? 0, т. е. на отрезке [х0
    , х1
    ] лежит не менее одного корня уравнения. Найдём середину отрезка х2
    =(х0
    +х1
    )/2 и вычислим f(х2
    ). Из двух половин отрезка выберем ту, для которой выполняется условие
    f (х2
    ) f(хгран
    .) ? 0, так как один из корней лежит на этой половине. Затем новый отрезок делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис 1.2).

  4. JonaH Ответить


    Тип урока:     Изучение и закрепление новых
    знаний.

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

    Продолжительность занятия:     два урока.

    Цель:     Научиться решать уравнения с заданной
    точностью на заданном отрезке.

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

    Методы обучения:     наглядный,
    исследовательский, практический.

    Оборудование:
    компьютер;
    локальная сеть;
    проектор.

    Программное обеспечение:
    Операционная система Windows;
    Microsoft Excel из пакета Microsoft Office;
    Microsoft Visual Basic 6.0.

    План урока:
    Организационный момент.
    Создание проблемной ситуации.
    Использование графического метода для
    приближенного решения уравнений в электронных
    таблицах.
    Изучение метода половинного деления при
    решении уравнений.
    Моделирование листа электронных таблиц для
    приближенного решения уравнения методом
    половинного деления.
    Моделирование проекта “Приближенное решение
    уравнения” на объектно-ориентированном языке
    Visual Basic 6.0.
    Компьютерный эксперимент.
    Анализ полученных результатов.
    Подведение итогов урока.

    Урок 1.
    Ход урока
    1. Организационный момент.
    Приветствие учителя.
    2. Создание проблемной ситуации.
    – Сегодня нам предстоит решить задачу
    нахождения приближенного корня уравнения cos(x)=x,
    используя различные программные средства.
    Запишите тему урока: “Приближенное решение
    уравнений разными инструментальными
    средствами.”
    – Пока вы не знаете никаких математических
    приемов решения этого уравнения, но знаете
    программу, в которой можно приближенно решить
    его графическим способом. Какая это программа?
    (Microsoft Excel.)
    3. Использование графического метода для
    приближенного решения уравнений в электронных
    таблицах.
    – В чем смысл метода? (Нужно построить график
    функции y = cos(x)–x на некотором отрезке,
    абсцисса точки пересечения графика с осью OX
    является корнем уравнения cos(x)=x.)
    – Что нужно определить для построения графика?
    (Отрезок, на котором существует корень.)
    – Сделайте это математическим методом.
    (Множеством значений левой части уравнения,
    функции y = cos(x), является отрезок [-1; 1].
    Поэтому уравнение может иметь корень только на
    этом отрезке.)
    – Итак, найдите приближенный корень
    уравнения cos(x)=x на отрезке [-1; 1] с шагом,
    например, 0,1 в программе Microsoft Excel.

    Рисунок 1
    – Приближенный корень уравнения х=0,75. Однако
    это приближение не обладает высокой точностью.
    Для нахождения приближенного корня уравнения с
    указанной заранее точностью используются
    математические методы, в частности, метод
    половинного деления.
    4. Изучение метода половинного деления при
    решении уравнений.
    Рассмотрим непрерывную функцию f(х), такую, что
    корень данного уравнения является точкой
    пересечения графика этой функции с осью ОХ.
    Идея метода половинного деления состоит в
    сведении первоначального отрезка [а; b], на
    котором существует корень уравнения, к отрезку
    заданной точности h.
    Процесс сводится к последовательному делению
    отрезка пополам точкой с=(а+b)/2 и отбрасыванию
    половины отрезка ([a; c] или [c; b]), на которой корня
    нет. Выбирается тот отрезок, на концах которого
    функция принимает значения разных знаков, т.е.
    произведение этих значений отрицательно.
    Функция на этом отрезке пересекает ось абсцисс.
    Концам этого отрезка вновь присваивают
    обозначения a, b.
    Это деление продолжается до тех пор, пока длина
    отрезка не станет меньше удвоенной точности, т.е.
    пока не выполнится неравенство (b-a)/2cos(x)=x с
    точностью 0,001. Решим поставленную задачу с
    использованием Microsoft Excel.
    5. Моделирование листа электронных таблиц
    для приближенного решения уравнения методом
    половинного деления.
    (Построение макета листа ведется совместно с
    учениками)
    Исходные значения границ отрезка a и b запишем в
    ячейки А4 и В4, в ячейке С4 получим середину
    заданного отрезка, в ячейках D4 и Е4 – значения
    функции f(х) на концах отрезка [a; c], в ячейке F4
    будем определять длину отрезка [а; b], необходимую
    точность укажем в ячейке H4. В ячейку G4 запишем
    формулу нахождения корня по правилу: если длина
    текущего отрезка соответствует требуемой
    точности, то в качестве корня уравнения примем
    значение середины этого отрезка. Мы уже знаем,
    что корень в нашем случае не найдется за один шаг,
    поэтому чтобы при копировании формулы из ячейки
    G4 адрес ячейки Н4 не менялся используем
    абсолютную адресацию.
    В пятой строке запишем значения, полученные
    после первого шага деления исходного отрезка
    пополам. В ячейки А5 и В5 нужно вписать формулы
    определения границ нового отрезка. В ячейки С4, D4,
    E4, F4, G4 формулы копируются из ячеек С5, D5, E5, F5, G5
    соответственно.
    Таким образом, в режиме формул лист электронной
    таблицы примет следующий вид:

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

    Урок 2.
    6. Моделирование проекта “Приближенное
    решение уравнения” на объектно-ориентированном
    языке Visual Basic 6.0.
    (Построение макета формы и написание
    программного кода ведется учащимися
    самостоятельно: индивидуально или в группах)
    Форма:

    Рисунок 3
    Программный код для кнопки Корень уравнения
    cos(x)=x    :
    Private Sub Command1_Click()
    a = Val(Text1)
    b = Val(Text2)
    e = Val(Text3)
    While (b – a) / 2 >= e
    c = (a + b) / 2
    fa = Cos(a) – a
    fc = Cos(c) – c
    If fa * fc < 0 Then b = c Else a = c Wend Text4 = (a + b) / 2 End Sub 7. Компьютерный эксперимент.
    (Учащиеся выполняют проект в электронных
    таблицах, выписывают результат в тетрадь. Затем
    выполняют проект на языке Visual Basic, выписывают
    результат в тетрадь.)
    Проект в электронных таблицах – Приложение 1.
    Проект на языке Visual Basic –
    Приложение 2.
    8. Анализ полученных результатов.
    (Учащиеся делают вывод, что результаты решения
    уравнения cos(x)=x, полученные с использованием
    разных инструментальных средств, одинаковые.)
    9. Подведение итогов урока.

  5. Adoradwyn Ответить

    Реферат по курсу
    численных методов выполнил студент группы РЭ–01-1
    Днепропетровский
    Национальный Университет
    Радиофизический
    факультет
    Кафедра физики
    СВЧ
    Днепропетровск
    2002
    1. Численное решение уравнений с одним неизвестным
    В
    данной работе рассматриваются метода приближённого вычисления действительных
    корней алгебраического или трансцендентного уравнения
    f(x)=0 (1.1)
    на
    заданном отрезке [a, b].
    Уравнение
    называется алгебраическим, если заданная функция есть полином n-ой степени:
    f(x) = P(x) = a0xn
    + a1xn- 1 + … + an-1 x + an
    = 0, a0 ¹ 0
    Требование
    a0 ¹ 0 обязательно, так как при
    невыполнении этого условия данное уравнение будет на порядок ниже.
    Всякое
    уравнение (1.1) называется
    трансцендентным, если в нём невозможно явным образом найти неизвестное, а можно
    лишь приближённо.
    Однако
    в число алгебраических уравнений можно также включить те уравнения, которое
    после некоторых преобразований, можно привести к алгебраическому.
    Те
    методы, которые здесь рассматриваются, применимы, как к алгебраическим
    уравнениям, так и к трансцендентным.
    Корнем
    уравнения (1.1) называется такое
    число x,
    где f(x)=0.
    При
    определении приближённых корней уравнения (1.1) необходимо решить две задачи:
    отделение
    корней, т. е. определение достаточно малых промежутков, в каждом из которых заключён
    один и только один корень уравнения (простой и кратный);
    уточнение
    корней с заданной точностью (верным числом знаков до или после запятой);
    Первую
    задачу можно решить, разбив данный промежуток на достаточно большое количество
    промежутков, где бы уравнение имело ровно один корень: на концах промежутков
    имело значения разных знаков. Там где данное условие не выполняется, те
    промежутки откинуть.
    Вторая
    задача решается непосредственно в методах рассмотренных ниже.
    При
    графическом отделении корней уравнения (1.1) нужно последнее преобразовать к виду:
    j1(x)=j2(x) (2.1)
    и
    построить графики функций y1=j1(x), y2=j2(x).
    Действительно,
    корнями уравнения (1.1)
    f(x) = j1(x) – j2(x) = 0
    являются
    абсциссы точек пересечения этих графиков (и только они).
    Из
    всех способов, какими можно уравнение (1.1) преобразовать к виду (2.1) выбираем тот, который обеспечивает
    наиболее простое построение графиков y1=j1(x) и y2=j2(x). В частности можно взять j2(x) = 0 и тогда придём к построению
    графика функции (1.1), точки
    пересечения которого с прямой y2=j2(x)=0, т. е. с осью абсцисс, и есть
    искомые корни уравнения (1.0).
    Условия,
    наложенные на функцию f(x) на отрезке [a, b].
    Будем
    предполагать, что функция f(x) непрерывна на отрезке [a, b] (для метода хорд можно потребовать на
    интервале) и имеет на этом интервале
    первую и вторую производные, причём обе они знакопостоянны (в частности
    отличны от нуля). Будем также предполагать, что функция f(x) принимает на концах отрезка значения разного знака. В силу
    знакопостоянства первой производной функция f(x)
    строго монотонна, поэтому при сделанных предположениях уравнение (1.1) имеет в точности один корень на
    интервале (a, b).
    2. Метод дихотомии

    Этот
    метод ещё называется методом вилки.
    Нам
    необходимо найти корень уравнения (1.1)
    на отрезке [a, b]. Рассмотрим отрезок [x0, x1]: [x0, x1]I[a, b]. Пусть мы нашли такие точки х0,
    х1, что f (х0)
    f(х1) ?
    0, т. е. на отрезке [х0, х1] лежит не менее одного корня
    уравнения. Найдём середину отрезка х2=(х0+х1)/2
    и вычислим f(х2).
    Из двух половин отрезка выберем ту, для которой выполняется условие
    f (х2) f(хгран.) ?
    0, так как один из корней лежит на этой половине. Затем новый отрезок делим
    пополам и выберем ту половину, на концах которой функция имеет разные знаки, и
    т. д. (рис 1.2).

    рис.
    1.2
    Если
    требуется найти корень с точностью Е, то продолжаем деление пополам до тех пор,
    пока длина отрезка не станет меньше 2Е. Тогда середина последнего отрезка  даст значение корня с требуемой точностью.   Дихотомия проста и очень надёжна. К простому  корню она сходится для любых непрерывных функций
    в том числе и не дифференцируемых; при
    этом она устойчива к ошибкам округления. Скорость сходимости не велика; за одну
    итерацию точность увеличивается примерно вдвое, т. е. уточнение трёх цифр
    требует 10 итераций. Зато точность ответа гарантируется.
    Приступим
    к доказательству того, что если непрерывная функция принимает на концах
    некоторого отрезка [a, b] значения разных знаков, то
    методом дихотомии однозначно будет найден корень.
    Предположим
    для определённости, что функция f(x) принимает на левом конце
    отрезка [a, b] отрицательное значение, а
    на правом – положительное:
    f(a) 0.
    Возьмём
    среднюю точку отрезка [a,
    b], h=(a+b)/2 и
    вычислим значение в ней функции f(x). Если f(h)=0, то утверждение теоремы доказано: мы нашли такую точку, где
    функция обращается в нуль. Если f(h)¹ 0, тогда из отрезков
    [a, h] и [h, b]
    выберем один из них тот, где функция на его концах принимает значения разных
    знаков. Обозначим его [a1,
    b1]. По
    построению: f(a1)<0, f(b1)>0. Затем среднюю точку
    отрезка [a1,
    b1] точку h1 и проведём тот же алгоритм нахождения
    другого отрезка [a2,
    b2] где бы
    по построению f(a2)<0, f(b2)>0. Будем продолжать
    этот процесс. В результате он либо оборвётся на некотором шаге n в силу того, что f(hn)=0, либо будет
    продолжаться неограниченно. В первом случае вопрос о существовании корня
    уравнения f(x)=0 решён, поэтому
    рассмотрим второй случай.
    Неограниченное
    продолжение процесса даёт последовательность отрезков [a, b], [a1,
    b1], [a2, b2],… Эти отрезки
    вложены друг в друга – каждый последующий отрезок принадлежит всем предыдущим:
    an ? an+ 1 < bn+ 1 ? bn (1.2) причём: f(an) < 0, f(bn) > 0
    Длины
    отрезков с возрастанием номера n
    стремятся к нулю:

    Рассмотрим
    левые концы отрезков. Согласно (1.2) они образуют монотонно убывающую
    ограниченную последовательность {an}. Такая последовательность имеет
    предел, который можно обозначить через c1:
    Согласно
    (1.1) и теореме о переходе к пределу в неравенствах имеем:
    c1
    ?
    bn (2.2)
    Теперь
    рассмотрим правые концы отрезков. Они образуют монотонно не возрастающую ограниченную
    последовательность {bn}, которая тоже имеет предел. Обозначим его
    через с2: . Согласно неравенству (2.1) пределы с1 и с2
    удовлетворяют неравенству с1 ? с2. Итак,
    an ?
    с1 < с2 ? bn, и следовательно: с2-с1 ? bn - an=(b-a)/2n. Таким образом, разность с2-с1 меньше любого наперёд заданного положительного числа. Это означает, что с2-с1=0, т. е.: с1=с2=с Найденная точка интересна тем, что она является единственной общей точкой для всех отрезков построенной последовательности Используя непрерывность функции f(x), докажем, что она является корнем уравнения f(x)=0. Мы знаем, что f(an)<0. Согласно определению непрерывности и возможности предельного перехода в неравенствах, имеем: f(c)=lim f(an)?0 (3.2) Аналогично, учитывая, что f(bn)³0, получаем, что: f(c)=lim f(bn) ³0 (4.2) Из (3.2) и (4.2) следует, что f(c)=0. т. е. с – корень уравнения. Процесс построения последовательности вложенных стягивающих отрезков методом вилки (дихотомии) является эффективным вычислительным алгоритмом решения уравнения f(x)=0. На n-ом шаге процесса получаем: an ? c ? bn Это двойное неравенство показывает, что число an определяет корень с недостатком, а число bn с избытком, с ошибкой не превышающей длину отрезка Dn=bn-an=(b-a)/2n. При увеличении n ошибка стремится к нулю по закону геометрической прогрессии со знаменателем q=0.5. Если задана требуемая точность e>0, то чтобы её
    достигнуть достаточно сделать число шагов N, не превышающее log2[(b-a)/e]: N>log2[(b-a)/e].
    3. Метод итераций
    Этот
    метод называется ещё методом последовательных приближений.
    Пусть
    нам необходимо найти корень уравнения (1.1) на некотором отрезке [a, b].
    Предположим,
    что уравнение (1.0) можно переписать в виде:
    x=j(x) (1.3)
    Возьмём
    произвольное значение x0
    из области определения функции j(x) и будет строить
    последовательность чисел {xn},
    определённых с помощью рекуррентной формулы:
    xn +1=j(xn), n=0, 1, 2, … (2.3)
    Последовательность
    {xn}
    называется итерационной последовательностью. При её изучении встают два
    вопроса:
    Можно ли процесс вычисления чисел xn продолжать неограниченно, т. е. будут ли числа xn принадлежать отрезку [a, b] ?
    Если итерационный процесс (2.3)
    бесконечен, то как ведут себя числа xn при n®¥
    Исследование
    этих вопросов показывает, что при определённых ограничениях на функцию j(x) итерационная последовательность
    является бесконечной и сходится к корню уравнения (1.3).
    , c=j(c) (3.3)
    Однако
    для того, чтобы провести это исследование нам нужно ввести новое понятие.
    Говорят,
    что функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, если существует
    такая постоянная a,
    что для любых x1,
    x2, принадлежащих
    отрезку [a, b] имеет место неравенство:
    |
    f(x1) – f(x2)| ? a|x1 – x2| (4.3)
    Величину
    a
    в этом случае называют постоянной Липшица.
    Если
    функция f(x), удовлетворяет на отрезке
    [a, b] условию Липшица, то она непрерывна на
    нём. Действительно, пусть x0
    – произвольная точка отрезка. Рассмотрим приращение функции f(x) в этой точке:
    Df=f(x0+Dx) – f(x0)
    и
    оценим его с помощью неравенства (4.3)
    |Df | ? a|Dx|
    Таким
    образом, , что означает непрерывность функции f(x).
    Условие
    Липшица имеет простой геометрический смысл. Возьмём не графике функции y=f(x) две произвольные точки M1 и M2 с координатами
    (x1, f(x1)) и (x2, f(x2)). Напишем уравнение прямой линии, проходящей через
    эти точки:
    y=f(x1) + k(x-x1)
    где
    k– тангенс угла наклона
    прямой у оси Оx и
    определяется формулой:

    Если
    функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, то при произвольном
    выборе точек M1
    и M2 имеем |k|?a.
    Таким образом, с геометрической точки зрения условие Липшица означает
    ограниченность тангенса угла наклона секущих, проведённых через всевозможные
    пары точек графика функции y=f(x).


    рис
    2.3 геометрическая иллюстрация условия Липшица.


    рис
    3.3 геометрическая иллюстрация cвязи условия Липшица с предположением о
    дифференцируемости функции.
    Предположим,
    что функция f(x) имеет на отрезке [a, b] ограниченную производную:
    |
    f ¢(x)| ? m;
    тогда она удовлетворяет условию Липшица с постоянной a=m. Для доказательс- тва этого
    утверждения воспользуемся формулой конечных приращений Лагранжа:
    f(x2) – f(x1) = f ¢(x)(x2-x1) (5.3)
    где
    x1, x2,
    – произвольные точки отрезка [a,
    b] x,
    – некоторая точка отрезка [x1,
    x2]. Возьмём
    модуль обеих частей равенства (4.3) и заменим в правой части | f ‘(x)| на m. В результате по- лучим неравенство
    (4.3) с a=m. Рис.2.3 даёт
    геометрическую иллюстрацию установленного свойства. Согласно формуле Лагранжа
    (5.3) каждой секущей графика функции y = f(x) мож- но поставить в
    соответствие параллельную её касательную. Поэтому наибольший тангенс угла
    наклона касательных, и его можно оценить той же константой m: |k| ?
    m.
    Познакомившись
    с условием Липшица, перейдём к изучению итерационной последовательности,
    предполагая, что уравнение имеет корень x=c.
    Существование этого корня можно установить с помощью качественного
    предварительного исследования уравнения с применением теоремы о существовании
    корня непрерывной функции.
    Теорема о существовании корня непрерывной функции 
    Если
    функция f(x) непрерывна на отрезке [a, b] и принимает на его концах значения
    разных знаков, то на этом отрезке существует, по крайней мере, один корень
    уравнения f(x).
    Теорема
    о сходимости итерационной последовательности
    Пусть
    с – корень уравнения (2.3) и пусть функция j(x) удовлетворяет на некотором отрезке [c-d, c+d] (d>0) условию Липшица с
    постоянной a<1.
    Тогда при любом выборе x0
    на отрезке [c-d, c+d] существует бесконечная
    итерационная последовательность {xn} и эта последовательность сходится к корню x=c, который является единственным
    решением уравнения (1.3) на отрезке [c-d,
    c+d].
    Сформулированная
    теорема имеет очень простой смысл. Будем говорить, что функция j
    осуществляет отображение точки x
    на точку y=j(x). Тогда условие Липшица с
    постоянной a<1
    означает, что отображение j является сжимающим: расстояние между точками x1 и x2 больше, чем
    расстояние между их изображениями y1=j(x1)
    и y2=j(x2).
    Корень
    c является неподвижной
    точкой отображения j,
    он преобразуется сам в себя c=j(c). Поэтому каждый шаг в
    итерационном процессе, сжимая расстояния должен приближать члены
    последовательности {xn}
    к неподвижной точке c.
    После
    таких соображений поясняющих смысл теоремы, перейдём к её доказательству.
    Возьмём произвольную точку x0
    на отрезке [c-d, c+d], она отстоит от точки c не больше чем на d: |c-x0| ? d.
    Вычислим
    x1: x1=j(x0), при этом x1-c =j(x0)-j(c). Разность j(x0)-j(c) можно оценить с помощью условия
    Липшица:
    |x1-c| = |j(x0)-j(c)| ?
    |x0-c| ? ad. (6.3)
    Неравенство
    (6.3) показывает, что x1
    принадлежит отрезку [c-d, c+d] и расположен ближе к
    точке c, чем x0.
    Продолжим
    построение итерационной последовательности. Вычислим x2: x2=j(x1), при этом:
    |x2-c| = |j(x1)-j(c)| ? a|x1-c| ? a2|x0-c| ? a2d
    Точка
    x2 опять
    принадлежит отрезку [c-d, c+d] и расположена ближе к
    точке c, чем точка x1, т.е. мы
    приблизились к c.
    По
    индукции легко доказать, что последующие итерации также существуют и
    удовлетворяют неравенствам.
    |xn-c| ? an |x0-c| ? and (7.3)
    Отсюда
    следует, что:
    , т. е.
    Остаётся
    доказать, что корень x=c (1.3) является единственным
    решением уравнения на отрезке [c-d, c+d].
    Действительно, допустим, что существует ещё один корень x=c1.
    Примем
    c1 за
    нулевое приближение и будем строить итерационную последователь- ность (2.3).
    Тогда с учётом (7.3) получим xn=c1 (n=0, 1, 2, …). С другой
    стороны, по доказанному , т. е. c1=c. Никаких других решений
    уравнение на отрезке иметь не может.
    Сходимость
    итерационной последовательности к корню уравнения (1.3) может быть использована
    для приближённого определения корня с любой степенью точности. Для этого нужно
    только провести достаточное количество итераций.
    4. Быстрота сходимости процесса итераций
    Используем
    теперь производную функции j(x)
    для оценки скорости сходимости итераций при решении уравнения х=j(x). Нужно оценить скорость, с
    которой убывают погрешности an=x-xn приближённых значений х1, … , хn, … корня x.

    рис
    1.4
    Можно
    заметить, что справедливы равенства x=j(x) и хn+ 1=j(хn).
    Из них вытекает, что:
    an+ 1= x-хn+ 1=j(x)-j(хn)
    Но
    по формуле Лагранжа имеем:
    j(x)-j(хn)= j ¢(cn)·( x-xn)= j ¢(cn) ·an
    где
    cn – точка
    лежащая между точками x и хn.
    Поэтому:
    an+ 1=j ¢(cn) ·an (1.4)
    Из
    равенства (1.4) вытекает следующий вывод:
    Пусть
    x
    – корень уравнения x=j (x) – лежит на отрезке [a, b]. Если на этом отрезке выполняется
    неравенство |j
    ¢(x)|1,
    то
    процесс итераций расходится.
    Особенно
    быстро сходится процесс последовательных приближений, если в точке x
    производная функции j(x) обращается в нуль. В этом
    случае по мере приближения к x, значение j ¢(x) стремится к нулю. Так как:
    |an+ 1|=|j ¢(cn)|·|an|
    то
    сходимость процесса ускоряется по мере приближения к точке x.
    Однако
    то же самое можно наблюдать в методе Ньютона, при замене f(x)=0 на  имеем: и её производная: в точке x: f(x)=0 –
    в методе Ньютона наблюдается ускорение сходимости процесса приближений.
    5. Метод касательных (метод Ньютона)
    Метод
    касательных, связанный с именем И. Ньютона, является одним из наиболее
    эффективных численных методов решения уравнений. Идея метода очень проста.
    Возьмём производную точку x0
    и запишем в ней уравнение касательной к графику функции f(x):
    y=f(x0)+ f ¢(x) (x-x0) (1.5)
    Графики
    функции f(x) и её касательной близки
    около точки касания, поэтому естественно ожидать, что точка x1 пересечения касательной с
    осью Ox будет
    расположена недалеко от корня c
    (рис. 1.5)
    Для
    определения точки имеем уравнение:
    f(x0)+ f ¢(x0) (x1-x0)=0
    таким
    образом: x1=x0 – f (x0)/ f ¢(x0) (2.5)
    Повторим
    проделанную процедуру: напишем уравнение касательной к графику функции f(x) при x=x1 и найдём для неё точку пересечения x2 с осью Ox (см.
    рис.1.5) x2=x1 – f (x1)/ f ¢(x1). Продолжая этот процесс,
    получим последовательность {xn},
    определён- ную с помощью рекуррентной формулы:
    xn+ 1=xn – f (xn)/ f ¢(xn), n=0, 1, 2, … (3.5)

    рис.
    1.5
    Построение
    последовательности  {xn}по методу касательных
    При
    исследовании этой последовательности, как и последовательности метода итераций,
    встают два вопроса:
    Можно
    ли процесс вычисления чисел xn
    продолжать неограниченно, т. е. будут ли числа xn принадлежать
    отрезку [a, b] ?
    Если
    процесс (3.5) бесконечен, то как ведёт себя последовательность {xn} при n®¥ ?
    При
    анализе этих вопросов предположим, что корень x=c является внутренней точкой отрезка [a, b] (a0, | f ¢¢(x)|?M, xI[a, b], (4.5)
    и
    докажем следующую теорему.
    Теорема
    о сходимости метода касательных.
    Если
    функция f(x) удовлетворяет условиям,
    сформулированным п.1., то найдётся такое d: 0 (6.5)
    и
    оценим полученное выражение. Согласно неравенствам (4.5):
     (7.5)
    Для
    дальнейшей оценки || воспользуемся непрерывностью функции f(x) и равенством её нулю в точке x= с:
     (8.5)
    Положим
    e=m2/(2M)
    Тогда
    в силу (8.5) для данного e можно указать такое d: 0     выполняется
    неравенство:
     (9.5)
    Учитывая
    это, получим:
     (10.5)
    Таким
    образом, функция j(x) удовлетворяет на отрезке [c-d, c+d] I [a, b] условию Липшица с постоянной a=0.5<1. Это означает,
    что уравнение (5.5) можно решать методом итераций: при любом выборе нулевого
    приближения x0
    на отрезке [c-d, c+d] существует бесконечная
    последовательность {xn},
    xn+1=j(xn), n=0, 1, 2, …, сходящаяся к корню x=c.
    Теперь
    нам остаётся заметить, что итерационной последовательностью для уравнения
    (5.5), сходимость которой мы только что установили, является последовательность
    (3.5) метода касательных. Теорема доказана.
    Требование
    близости нулевого приближения x0
    к искомому корню c
    является существенным для метода касательных. На рис.2.5 изображён график, где
    х0 выбрано неправильно, то есть расстояние сх0>ас, так
    как ас
    рис.
    2.5 Случай, когда процесс построения
    последовательности {xn}
    обрывается из-за плохого выбора нулевого приближения
    6. Первые приближения для метода касательных
    Первые
    нулевые приближения для метода Ньютона, для итерационной последовательности,
    можно так же найти другим путём. Если нам известно, что функция f(x) на отрезке [a, b] непрерывна и дважды дифференцируема, и имеет ровно один
    корень, тогда можно взять за нулевое приближение значение одного из концов
    отрезка [a, b] в зависимости от знака
    второй производной, иначе при первом же приближении можно попасть за пределы
    отрезка [a, b] (рис. 1.6).

    То
    есть можно сформулировать следующее правило:
    Пусть
    в точках a и b функция f(x) имеет различные знаки, причём на отрезке [a, b] вторая производная положительна. Тогда за начальное
    приближение х1 надо выбирать ту из точек a или b, в которой функция f(x)
    принимает положительное значение. Если же на отрезке [a, b] вторая производная
    отрицательна, то за начальное
    приближение x1
    надо выбирать ту точку, в которой функция f(x)
    принимает отрицательное значение.
    7. Метод секущих

    В
    методе Ньютона (касательных) требуется вычислять производную функции, что не
    всегда удобно. Можно заменить производную функции первой разделённой разностью,
    найденной по двум последним итерациям, т. е. заменить касательную секущей.
    Тогда вместо процесса  получим:
     (1.7)
    для
    начала процесса необходимо задать х0 и х1 (рис. 1.7).
    Такие процессы, где для вычисления очередного приближения надо знать два
    предыдущих, называют двух шаговыми.
    Эти
    изменения сильно меняют характер итераций. Например, сходимость итераций может
    быть немонотонной не только вдали от корня, но и малой окрестности корня.
    Скорость сходимости также изменяется. Его можно оценить, разлагая все функции в
    (1.7) по формуле Тейлора с центром . Получим с точностью до бесконечно малых более высокого
    порядка:
      (2.7)
    Решение
    этого рекуррентного соотношения естественно искать в виде аналогичном методу
    Ньютона: . Подставляя эту форму в соотношение (2.6), получим:
    ab=1, b2
    – b
    – 1 = 0 (3.7)
    Только
    положительный корень b квадратного уравнения (3.6) соответствует убыванию
    ошибки, т. е. сходящемуся процессу. Следовательно, в методе секущих

    ,
    в
    то время как в методе Ньютона ошибка убывает быстрей (соответствуя b=2).
    Но в методе на каждой итерации надо вычислять и функцию, и производную, а в
    методе секущих – только функцию. Поэтому при одинаковом объёме вычисления в
    методе секущих можно сделать вдвое больше итераций и получить более высокую
    точность. Что является более приемлемым при численных расчётах на ЭВМ, чем
    метод касательных.
    В
    знаменателе формулы (1.7) стоит разность значений функции. Вдали от корня это
    несущественно; но вблизи корня, особенно корня высокой кратности, значения
    функции малы и очень близки. Возникает потеря значащих цифр, приводящая к
    «разболтке» счёта. Это ограничивает точность, с которой можно найти корень; для
    простых корней это ограничение невелико. Приводить к общему знаменателю
    уравнение (1.7) не следует: может увеличится потеря точности в расчётах.
    От
    «разболтки» страхуются так называемым приёмом Гарвика. Выбирают не очень малое e,
    ведут итерации до выполнения |xn+
    1-xn|8. Метод хорд, или линейной аппроксимации
    Рассмотрим
    задачу решения уравнения (1.1) методом хорд.
    Этот
    метод состоит в следующем. График функции f(x)
    заменяется её хордой, т. е. отрезком соединяющий концевые точки графика функции
    f(x): точки (a, f(a)) и (b, f(b)). Абсцисса х1 точки пересечения этой хорды с осью
    Ох и рассматривается, как первое приближение искомого корня (рис 1.8). Далее
    берётся тот из отрезков [a,
    x1] и [x1, b], на концах которого,
    функция f(x) принимает значения разного
    знака (далее будет показано, что при сделанных предположениях f(x) ¹
    0 и, следовательно, такой отрезок
    всегда существует), и к нему применяется тот же приём; получается второе
    приближение корня х2 и т. д. В результате образуется последовательность
    хn, n=1, 2, … которая, как это
    будет показано, при сделанных ограничениях на функцию f(x), сходится к корню уравнения f(x).
    Легко
    получить рекуррентные формулы для указанных чисел хn, n=1, 2,… Уравнение прямой, проходящее
    через крайние точки графика функции f(x)
    имеет вид:

     (1.8)
    Обозначим
    его правую часть через l(x), т. е. Запишем уравнение в
    виде:
    y = l(x)
    Найдём
    абсциссу х1 точки пересечения прямой (1.8) с осью Ох, т. е. Решим
    уравнение l(x)=0; получим:
     (2.8)
    Легко
    убедится, что:
    a < x1 < b (3.8) Это, например, следует из строгой монотонности и непрерывности функции l(x) и того, что на концах отрезка [a, b] она принимает значения разного знака: l(a)=f(a) и l(b)=f(b). Аналогично находим  n=1, 2, … (4.8)
    Покажем,
    что последовательность {xn}
    стремится к корню уравнения (1.0) монотонно.
    Предположим
    для определённости, что f ¢(x) и f ¢¢(x) >0, a f(x), a
    > x > b
    В
    частности, если х0 корень уравнения (1.1): f(x0) = 0, отсюда следует, что
    l(x0) > 0
    C (3.8) и (4.8) получаем:
    l(x) = 0, a > x1 > b
    Таким
    образом,
    l(x1) < l(x0) (5.8) но линейная функция l(x) строго монотонно возрастает, так как l(b) = f(b) >
    f(a) = l(a)
    поэтому
    из (5.8) следует x1 < x0 , заменяя теперь отрезок [a, b] отрезком [x1, b] и замечая, что f(x1) < 0 , аналогично можно доказать, что x1 < x2 < x0, далее по индукции получим: x1 < x2 < … < xn < … < x0, Таким образом, последовательность {xn}, будучи монотонной, сходится. Пусть lim xn = c, при n®¥ . Переходя к пределу при n®¥ в равенстве (4.8) получим f(c)=0, т. е. последовательность {xn} сходится к корню уравнения (1.1). Если | f ¢(x)|³m>0, a    , n =
    1, 2, …,
    Остальные
    случаи, т. е. случаи:
     ,
     ,
     
    рассматриваются
    аналогично разобранному (рис 2.8).


    рис.
    2.8
    9.
    Усовершенствованный метод хорд
    Если
    итерационная последовательность, полученная методом хорд, сходится, то скорость
    сходимости будет такой же, как и у метода итераций, – погрешность значения
    корня убывает, как геометрическая прогрессия. Существует усовершенствование
    способа хорд, дающее гораздо более быструю сходимость. В обычном методе хорд мы
    на каждом шагу используем один из концов отрезка [a, b] последнее получившееся приближение. Вместо этого можно
    использовать два последних приближения – ведь они ближе к искомому корню, чем
    концы отрезка [a, b].
     рис.1.9 а) б)
    Формула,
    при которой мы используем два последних приближения, имеет вид:
     (1.9)
    При
    этом а1 вычисляется по формуле:

    а
    а2 в зависимости от знаков f(a), f(b), f(a1),
    если f(a)0,
     , f(a1)<0
     , f(a1)>0
    Если
    случайно окажется, что точка а3, вычисленная по формуле (1.9), лежит
    за пределами отрезка [a,
    b], то на следующем
    шаге надо вместо этой точки взять ближайший к ней конец этого отрезка (рис.
    1.9, б). Оказывается, что сходимость усовершенствованного метода хорд гораздо
    быстрее, чем у обычного. Именно, если x – корень уравнения f(x)=0, то:
    |an+ 1|
    10.
    Комбинированный метод решения уравнений
    При
    решении уравнений часто комбинируют методы хорд и Ньютона. Если график функции y=f(x) обращён вогнутостью вверх, то находят точки а1 и х1
    по формулам:
     (1.10)
     (2.10)
    Если
    же график функции y=f(x) обращён вогнутостью вниз, то точку а1
    находят по формуле (1.10), а точку х1 – по формуле:
     (3.10)
    Как
    видно из рис.1.10 а) и б), корень x уравнения f(x)=0
    лежит обычно между полученными точками а1 и х1. Применяя
    снова к этим точкам формулы метода хорд и метода Ньютона, получают новую пару
    точек а2 и х2 и т. д.
    Таким
    путём получают две последовательности точек а1, а2, а3,
    …, an, … и x1, x2, x3, … , xn, …,
    приближаются с разных сторон к искомому корню x. Преимущество описанного
    метода состоит в том, что при нём получаются приближённые значения как с
    избытком так и с достатком.
    рис.1.10


    а)
    б)
    11. Заключительные замечания
    Ситуация,
    когда одну и ту же задачу можно решить многими способами, является довольно
    типичной. В таких случаях естественно возникает необходимость сравнения их
    между собой.
    При
    оценке эффективности численных методов существенное значение имеют различные
    свойства:
    универсальность;
    простота
    организации вычислительного процесса и контроля над точностью;
    скорость
    сходимости.
    Наиболее
    универсальным является метод деления пополам (дихотомии): он только требует
    непрерывности функции. Остальные методы накладывают более сильные ограничения.
    Во многих случаях это преимущество метода вилки может оказаться существенным.
    С
    точки зрения организации вычислительного процесса все виды численного
    нахождения корней уравнения очень просты. Однако и здесь метод деления пополам
    обладает некоторым преимуществом. Вычисления можно начинать с любого отрезка [a, b], на концах которого непрерывная
    функция f(x) принимает значения разных
    знаков. Процесс будет сходится к корню уравнения f(x)=0, причём на каждом шаге он даёт для корня двустороннюю
    оценку, по которой легко определить достигнутую точность. Сходимость же метода
    итераций или касательных зависит от того, насколько удачно выбрано нулевое
    приближение.
    Наибольшей
    скоростью сходимости обладает метод касательных. В случае, когда подсчёт
    значений функции f(x) сложен и требует больших
    затрат машинного времени, это преимущество становится определяющим. На вопрос о
    том, какой метод – метод итераций или дихотомия даёт большую скорость
    сходимости, однозначно ответить нельзя. При методе дихотомии знаменатель
    геометрической прогрессии убывания погрешности равен q=0.5, а при методе хорд он может
    принимать значения 0Список литературы
    А.
    Н. Тихонов, Д. П. Костомаров «Вводные лекции по прикладной математике»
    М.
    «Наука» 1984
    Л.
    Д. Кудрявцев «Математический анализ т. 2» М. 1984 «Наука»
    П.
    Ф. Фильчаков «Справочник по высшей математике» К. 1973 «Наукова Думка»
    Н.
    Н. Калиткин «Численные методы» М. «Наука» 1978
    Н.
    Я. Виленкин «Итерационные методы» М. «Наука» 1984
    Дата добавления: 10.03.2005

  6. Blackfire Ответить

    1.
    Приближенное  решение нелинейных
    уравнений
    Пусть
    дано уравнение с одним неизвестным

    ,
    (1.1)
    где f(x) – заданная алгебраическая или трансцендентная
    функция.
    Функция
    называется алгебраической, если для получения её значения нужно выполнить
    арифметические операции и возведение в степень с рациональным показателем.
    Примеры трансцендентных функций – показательная,
    логарифмическая, тригонометрические, обратные тригонометрические.
    Решить
    уравнение – значит найти все его корни, то есть те значения х,
    которые обращают уравнение в тождество, или доказать, что корней нет.
    В
    общем случае не существует формул, по которым определяются точные значения корней
    уравнения (1.1). Для отыскания корней используют приближенные методы, при
    этом корни находятся с некоторой заданной точностью ?.
    Это означает, что если x – точное значение корня уравнения, а x’-
    его приближенное значение с точностью ?, то |x – x’|
    ? ?. Если корень найден с точностью ?, то принято писать x = x ± ?.
    Будем
    предполагать, что уравнение (1.1) имеет лишь
    изолированные корни, то есть для каждого корня существует окрестность,
    не содержащая других корней этого уравнения.
    Приближенное
    решение уравнения состоит из двух этапов:
    1.
    Отделение
    корней    , то есть нахождение интервалов из области определения функции f(x), в каждом из
    которых содержится только один корень уравнения (1).
    2.
    Уточнение
    корней     до заданной точности.
    Отделение
    корней     можно проводить  графически и аналитически.
    Для
    того, чтобы графически отделить корни уравнения
    (1.1), строят график функции y = f(x). Абсциссы
    точек его пересечения с осью Ox есть
    действительные корни уравнения (рис. 1). Практически бывает удобнее заменить
    уравнение (1.1) равносильным ему уравнением

    ,                                          (1.2)
    где ?(x) и
    ?(x) – более простые функции, чем f(x). Абсциссы
    точек пересечения графиков функций y =
    ?(x) и y = ?(x)  дают корни
    уравнения (1.2), а значит и исходного уравнения (1.1) (рис.2).
    Аналитическое отделение
    корней основано на следующей теореме: если непрерывная на отрезке
    [a, b] функция y = f(x) принимает на
    концах отрезка значения разных знаков, т.е. f(a)·f(b) < 0, то внутри этого отрезка находится хотя бы один корень уравнения f(x) = 0;  если при этом производная f’(x) сохраняет знак внутри отрезка [a, b], то корень является единственным.
    Уточнение
    корней     заключается в сужении
    интервала изоляции корня и выполняется одним из специальных методов. Рассмотрим
    самый простой из них – метод половинного деления.
    Пусть
    корень отделён и принадлежит отрезку [a, b]. Находим середину отрезка [a, b] по формуле

    Если
    f(c) = 0, то с –
    искомый корень. Если f(c) ? 0, то в качестве нового отрезка изоляции
    корня [a1, b1]
    выбираем ту половину [a, c] или [c, b], на концах которой f(x) принимает
    значения разных знаков. Другими словами, если f(a) • f(c) < 0, то корень принадлежит отрезку [a, c], если f(a) • f(c) < 0  - отрезку [c, b]. Полученный отрезок снова делим  пополам, находим c1,
    вычисляем f(c1),
    выбираем отрезок [a2, b2] и т.д. Длина каждого нового отрезка вдвое меньше длины
    предыдущего, то есть за n шагов отрезок сократится в 2n
    раз. Как только будет выполнено условие

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

    Пример.  Пусть требуется
    решить уравнение

    с точностью ? = 0,0001. Отделим корень
    графически. Для этого преобразуем уравнение
    к виду

    и  построим  графики функций (рис. 4):

    Из рисунка видно, что абсцисса точки пересечения этих
    графиков принадлежит отрезку [0; 1].
    Подтвердим
    аналитически правильность нахождения отрезка изоляции корня. Для отрезка [0; 1] имеем:



    . Следовательно, корень отделён правильно.
    Уточнение корня выполним методом половинного деления.

    Первый шаг.


    Корень принадлежит отрезку


    Второй шаг.


    Корень принадлежит отрезку


    Третий шаг.


    Корень принадлежит отрезку

    Сведём
    результаты вычислений в таблицу.

  7. razhabov Ответить




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



    Отсюда следует, что корень находится на отрезке .
    Длина этого отрезка процесс по методу деления отрезка пополам следует закончить.
    Середина отрезка дает корень с заданной степенью точности .

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

    Рис. 5
    Для начала вычислений требуется задание одного начального приближения внутри отрезка . Первое приближение вычисляется через это начальное по формуле рис. 5:

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

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

    вычисления по методу Ньютона следует продолжить.
    2. По рекуррентной формуле метода Ньютона вычислим

    вычисления по методу Ньютона можно закончить.

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

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

    Проверяем принцип сжатых отображений для выбранной нами итерирующей функции (рассматриваем один из множества возможных способов представления итерирующей функции).
    Проанализируем, как ведет себя функция на отрезке .
    Построим таблицу
    x
    -1
    -0,9
    -0,8
    -0,7
    -0,6
    -0,5
    -0,4
    -0,3
    -0,2
    -0,1
    0

    1,818
    1,587
    1,367
    1,158
    0,96
    0,773
    0,596
    0,431
    0,276
    0,133
    0
    Из таблицы видно, что концы отрезка, на котором выполняется условие , соответственно равны .
    Таким образом будем уточнять корень на отрезке с помощью следующего рекуррентного уравнения
    .
    Выберем в качестве начального приближения
    Сведем расчеты в таблицу
    Таблица 5
    №



    1
    -0,6
    -0,45891
    -0,766
    2
    -0,45891
    -0,57568
    0,642255
    3
    -0,57568
    -0,48169
    -0,51695
    4
    -0,48169
    -0,5593
    0,4268
    5
    -0,5593
    -0,4964
    -0,34597
    6
    -0,4964
    -0,54822
    0,285
    7
    -0,54822
    -0,50606
    -0,23188
    8
    -0,50606
    -0,54074
    0,19073
    9
    -0,54074
    -0,51245
    -0,15558
    10
    -0,51245
    -0,53569
    0,1278
    11
    -0,53569
    -0,51671
    -0,1044
    12
    -0,51671
    -0,53229
    0,0857
    13
    -0,53229
    -0,51962
    -0,069
    14
    -0,51962
    -0,52994
    0,057
    15
    -0,52994
    -0,5215
    -0,046
    На 15 шаге выполняется условие выхода из итерационного процесса . Отсюда следует, что корень уравнения найденный по методу простой итерации с точностью равен .

  8. Shalirad Ответить

    Министерство науки и образования Украины
    Днепропетровский Национальный Университет
    Радиофизический факультет
    Кафедра физики СВЧ
    Реферат по курсу
    численных методов:

    “Приближённые методы решения алгебраичекого уравнения”

    Выполнил:
    Студент
    группы РЭ?01-1
    Проверил:
    Доцент кафедры
    физики СВЧ К. В. Заболотный
    Днепропетровск 2002
    Содержание
    Численное решение уравнения, условия, наложенные на функцию, графический метод определения корней.
    Метод дихотомии.
    Метод итераций
    Быстрота сходимости процесса итераций
    Метод касательных
    Первые приближения для метода касательных
    Метод секущих
    Метод хорд
    Усовершенствованный метод хорд
    Комбинированный метод решения уравнения
    Заключительные замечания
    Список использованной литературы
    1. Численное решение уравнений с одним неизвестным
    В данной работе рассматриваются метода приближённого вычисления действительных корней алгебраического или трансцендентного уравнения
    f(x)=0 (1.1)
    на заданном отрезке [a, b].
    Уравнение называется алгебраическим, если заданная функция есть полином n-ой степени:
    f(x) = P(x) = a0xn + a1xn- 1 + … + an-1 x + an = 0, a0 ? 0
    Требование a0 ? 0 обязательно, так как при невыполнении этого условия данное уравнение будет на порядок ниже.
    Всякое уравнение (1.1) называется трансцендентным, если в нём невозможно явным образом найти неизвестное, а можно лишь приближённо.
    Однако в число алгебраических уравнений можно также включить те уравнения, которое после некоторых преобразований, можно привести к алгебраическому.
    Те методы, которые здесь рассматриваются, применимы, как к алгебраическим уравнениям, так и к трансцендентным
    .
    Корнем уравнения (1.1) называется такое число ?, где f(?)=0.
    При определении приближённых корней уравнения (1.1) необходимо решить две задачи:
    отделение корней, т. е. определение достаточно малых промежутков, в каждом из которых заключён один и только один корень уравнения (простой и кратный);
    уточнение корней с заданной точностью (верным числом знаков до или после запятой);
    Первую задачу можно решить, разбив данный промежуток на достаточно большое количество промежутков, где бы уравнение имело ровно один корень: на концах промежутков имело значения разных знаков. Там где данное условие не выполняется, те промежутки откинуть.
    Вторая задача решается непосредственно в методах рассмотренных ниже.
    При графическом отделении корней уравнения (1.1) нужно последнее преобразовать к виду:
    ?1(x)=?2(x) (2.1)
    и построить графики функций y1=?1(x), y2=?2(x).
    Действительно, корнями уравнения (1.1)
    f(x) = ?1(x) – ?2(x) = 0
    являются абсциссы точек пересечения этих графиков (и только они).
    Из всех способов, какими можно уравнение (1.1) преобразовать к виду (2.1) выбираем тот, который обеспечивает наиболее простое построение графиков y1=?1(x) и y2=?2(x). В частности можно взять ?2(x) = 0 и тогда придём к построению графика функции (1.1), точки пересечения которого с прямой y2=?2(x)=0, т. е. с осью абсцисс, и есть искомые корни уравнения (1.0).
    Условия, наложенные на функцию f(x) на отрезке [a, b].
    Будем предполагать, что функция f(x) непрерывна на отрезке [a, b] (для метода хорд можно потребовать на интервале) и имеет на этом интервале первую и вторую производные, причём обе они знакопостоянны (в частности отличны от нуля). Будем также предполагать, что функция f(x) принимает на концах отрезка значения разного знака. В силу знакопостоянства первой производной функция f(x) строго монотонна, поэтому при сделанных предположениях уравнение (1.1) имеет в точности один корень на интервале (a, b).
    2. Метод дихотомии
    Этот метод ещё называется методом вилки.
    Нам необходимо найти корень уравнения (1.1) на отрезке [a, b]. Рассмотрим отрезок [x0, x1]: [x0, x1]?[a, b]. Пусть мы нашли такие точки х0, х1, что f (х0) f(х1) ? 0, т. е. на отрезке [х0, х1] лежит не менее одного корня уравнения. Найдём середину отрезка х2=(х0+х1)/2 и вычислим f(х2). Из двух половин отрезка выберем ту, для которой выполняется условие
    f (х2) f(хгран.) ? 0, так как один из корней лежит на этой половине. Затем новый отрезок делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис 1.2).
    Если требуется найти корень с точностью Е, то про-
    должаем деление пополам до тех пор, пока длина отрезка
    не станет меньше 2Е. Тогда середина последнего отрезка
    даст значение корня с требуемой точностью.
    Дихотомия проста и очень надёжна. К простому
    корню она сходится для любых непрерывных функций
    в том числе и не дифференцируемых; при этом она устой-
    чива к ошибкам округления. Скорость сходимости не ве-
    лика; за одну итерацию точность увеличивается пример-
    но вдвое, т. е. уточнение трёх цифр требует 10 итераций.
    Зато точность ответа гарантируется. рис. 1.2
    Приступим к доказательству того, что если непрерывная функция принимает на концах некоторого отрезка [a, b] значения разных знаков, то методом дихотомии однозначно будет найден корень.
    Предположим для определённости, что функция f(x) принимает на левом конце отрезка [a, b] отрицательное значение, а на правом ? положительное:
    f(a) < 0, f(b) > 0.
    Возьмём среднюю точку отрезка [a, b], h=(a+b)/2 и вычислим значение в ней функции f(x). Если f(h)=0, то утверждение теоремы доказано: мы нашли такую точку, где функция обращается в нуль. Если f(h)? 0, тогда из отрезков [a, h] и [h, b] выберем один из них тот, где функция на его концах принимает значения разных знаков. Обозначим его [a1, b1]. По построению: f(a1)<0, f(b1)>0. Затем среднюю точку отрезка [a1, b1] точку h1 и проведём тот же алгоритм нахождения другого отрезка [a2, b2] где бы по построению f(a2)<0, f(b2)>0. Будем продолжать этот процесс. В результате он либо оборвётся на некотором шаге n в силу того, что f(hn)=0, либо будет продолжаться неограниченно. В первом случае вопрос о существовании корня уравнения f(x)=0 решён, поэтому рассмотрим второй случай.
    Неограниченное продолжение процесса даёт последовательность отрезков [a, b], [a1, b1], [a2, b2],… Эти отрезки вложены друг в друга ? каждый последующий отрезок принадлежит всем предыдущим:
    an ? an+ 1 < bn+ 1 ? bn (1.2) причём: f(an) < 0, f(bn) > 0
    Длины отрезков с возрастанием номера n стремятся к нулю:
    Рассмотрим левые концы отрезков. Согласно (1.2) они образуют монотонно убывающую ограниченную последовательность {an}. Такая последовательность имеет предел, который можно обозначить через c1:
    Согласно (1.1) и теореме о переходе к пределу в неравенствах имеем:
    c1 ? bn (2.2)
    Теперь рассмотрим правые концы отрезков. Они образуют монотонно не возрастающую ограниченную последовательность {bn}, которая тоже имеет предел. Обозначим его через с2: . Согласно неравенству (2.1) пределы с1 и с2 удовлетворяют неравенству с1 ? с2. Итак, an ? с1 < с2 ? bn, и следовательно: с2-с1 ? bn - an=(b-a)/2n. Таким образом, разность с2-с1 меньше любого наперёд заданного положительного числа. Это означает, что с2-с1=0, т. е.: с1=с2=с Найденная точка интересна тем, что она является единственной общей точкой для всех отрезков построенной последовательности Используя непрерывность функции f(x), докажем, что она является корнем уравнения f(x)=0. Мы знаем, что f(an)<0. Согласно определению непрерывности и возможности предельного перехода в неравенствах, имеем: f(c)=lim f(an)?0 (3.2) Аналогично, учитывая, что f(bn)?0, получаем, что: f(c)=lim f(bn) ?0 (4.2) Из (3.2) и (4.2) следует, что f(c)=0. т. е. с ? корень уравнения. Процесс построения последовательности вложенных стягивающих отрезков методом вилки (дихотомии) является эффективным вычислительным алгоритмом решения уравнения f(x)=0. На n-ом шаге процесса получаем: an ? c ? bn Это двойное неравенство показывает, что число an определяет корень с недостатком, а число bn с избытком, с ошибкой не превышающей длину отрезка ?n=bn-an=(b-a)/2n. При увеличении n ошибка стремится к нулю по закону геометрической прогрессии со знаменателем q=0.5. Если задана требуемая точность ?>0, то чтобы её достигнуть достаточно сделать число шагов N, не превышающее log2[(b-a)/?]: N>log2[(b-a)/?].
    3. Метод итераций
    Этот метод называется ещё методом последовательных приближений.
    Пусть нам необходимо найти корень уравнения (1.1) на некотором отрезке [a, b].
    Предположим, что уравнение (1.0) можно переписать в виде:
    x=?(x) (1.3)
    Возьмём произвольное значение x0 из области определения функции ?(x) и будет строить последовательность чисел {xn}, определённых с помощью рекуррентной формулы:
    xn +1=?(xn), n=0, 1, 2, … (2.3)
    Последовательность {xn} называется итерационной последовательностью. При её изучении встают два вопроса:
    Можно ли процесс вычисления чисел xn продолжать неограниченно, т. е. будут ли числа xn принадлежать отрезку [a, b] ?
    Если итерационный процесс (2.3) бесконечен, то как ведут себя числа xn при n??
    Исследование этих вопросов показывает, что при определённых ограничениях на функцию ?(x) итерационная последовательность является бесконечной и сходится к корню уравнения (1.3).
    , c=?(c) (3.3)
    Однако для того, чтобы провести это исследование нам нужно ввести новое понятие.
    Говорят, что функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, если существует такая постоянная ?, что для любых x1, x2, принадлежащих отрезку [a, b] имеет место неравенство:
    | f(x1) – f(x2)| ? ?|x1 – x2| (4.3)
    Величину ? в этом случае называют постоянной Липшица.
    Если функция f(x), удовлетворяет на отрезке [a, b] условию Липшица, то она непрерывна на нём. Действительно, пусть x0 ? произвольная точка отрезка. Рассмотрим приращение функции f(x) в этой точке:
    ?f=f(x0+?x) ? f(x0)
    и оценим его с помощью неравенства (4.3)
    |?f | ? ?|?x|
    Таким образом, , что означает непрерывность функции f(x).
    Условие Липшица имеет простой геометрический смысл. Возьмём не графике функции y=f(x) две произвольные точки M1 и M2 с координатами (x1, f(x1)) и (x2, f(x2)). Напишем уравнение прямой линии, проходящей через эти точки:
    y=f(x1) + k(x-x1)
    где k? тангенс угла наклона прямой у оси Оx и определяется формулой:
    Если функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, то при произвольном выборе точек M1 и M2 имеем |k|??. Таким образом, с геометрической точки зрения условие Липшица означает ограниченность тангенса угла наклона секущих, проведённых через всевозможные пары точек графика функции y=f(x).
    рис 2.3 рис 3.3
    геометрическая иллюстрация геометрическая иллюстрация
    условия Липшица. cвязи условия Липшица с пред-
    положением о дифференциру-
    емости функции.
    Предположим, что функция f(x) имеет на отрезке [a, b] ограниченную производную:
    | f ?(x)| ? m; тогда она удовлетворяет условию Липшица с постоянной ?=m. Для доказательс- тва этого утверждения воспользуемся формулой конечных приращений Лагранжа:
    f(x2) ? f(x1) = f ?(?)(x2-x1) (5.3)
    где x1, x2, – произвольные точки отрезка [a, b] ?, – некоторая точка отрезка [x1, x2]. Возьмём модуль обеих частей равенства (4.3) и заменим в правой части | f ?(x)| на m. В результате по- лучим неравенство (4.3) с ?=m. Рис.2.3 даёт геометрическую иллюстрацию установленного свойства. Согласно формуле Лагранжа (5.3) каждой секущей графика функции y = f(x) мож- но поставить в соответствие параллельную её касательную. Поэтому наибольший тангенс угла наклона касательных, и его можно оценить той же константой m: |k| ? m.
    Познакомившись с условием Липшица, перейдём к изучению итерационной последовательности, предполагая, что уравнение имеет корень x=c. Существование этого корня можно установить с помощью качественного предварительного исследования уравнения с применением теоремы о существовании корня непрерывной функции.
    Теорема о существовании корня непрерывной функции
    Если функция f(x) непрерывна на отрезке [a, b] и принимает на его концах значения разных знаков, то на этом отрезке существует, по крайней мере, один корень уравнения f(x).
    Теорема о сходимости итерационной последовательности
    Пусть с ? корень уравнения (2.3) и пусть функция ?(x) удовлетворяет на некотором отрезке [c-?, c+?] (?>0) условию Липшица с постоянной ?<1. Тогда при любом выборе x0 на отрезке [c-?, c+?] существует бесконечная итерационная последовательность {xn} и эта последовательность сходится к корню x=c, который является единственным решением уравнения (1.3) на отрезке [c-?, c+?].
    Сформулированная теорема имеет очень простой смысл. Будем говорить, что функция ? осуществляет отображение точки x на точку y=?(x). Тогда условие Липшица с постоянной ?<1 означает, что отображение ? является сжимающим: расстояние между точками x1 и x2 больше, чем расстояние между их изображениями y1=?(x1) и y2=?(x2).
    Корень c является неподвижной точкой отображения ?, он преобразуется сам в себя c=?(c). Поэтому каждый шаг в итерационном процессе, сжимая расстояния должен приближать члены последовательности {xn} к неподвижной точке c.
    После таких соображений поясняющих смысл теоремы, перейдём к её доказательству. Возьмём произвольную точку x0 на отрезке [c-?, c+?], она отстоит от точки c не больше чем на ?: |c-x0| ? ?.
    Вычислим x1: x1=?(x0), при этом x1-c =?(x0)-?(c). Разность ?(x0)-?(c) можно оценить с помощью условия Липшица:
    |x1-c| = |?(x0)-?(c)| ? |x0-c| ? ??. (6.3)
    Неравенство (6.3) показывает, что x1 принадлежит отрезку [c-?, c+?] и расположен ближе к точке c, чем x0.
    Продолжим построение итерационной последовательности. Вычислим x2: x2=?(x1), при этом:
    |x2-c| = |?(x1)-?(c)| ? ?|x1-c| ? ?2|x0-c| ? ?2?
    Точка x2 опять принадлежит отрезку [c-?, c+?] и расположена ближе к точке c, чем точка x1, т.е. мы приблизились к c.
    По индукции легко доказать, что последующие итерации также существуют и удовлетворяют неравенствам.
    |xn-c| ? ?n |x0-c| ? ?n? (7.3)
    Отсюда следует, что:
    , т. е.
    Остаётся доказать, что корень x=c (1.3) является единственным решением уравнения на отрезке [c-?, c+?]. Действительно, допустим, что существует ещё один корень x=c1.
    Примем c1 за нулевое приближение и будем строить итерационную последователь- ность (2.3). Тогда с учётом (7.3) получим xn=c1 (n=0, 1, 2, …). С другой стороны, по доказанному , т. е. c1=c. Никаких других решений уравнение на отрезке иметь не может.
    Сходимость итерационной последовательности к корню уравнения (1.3) может быть использована для приближённого определения корня с любой степенью точности. Для этого нужно только провести достаточное количество итераций.
    4. Быстрота сходимости процесса итераций
    Используем теперь производную функции ?(x) для оценки скорости сходимости итераций при решении уравнения х=?(x). Нужно оценить скорость, с которой убывают погрешности ?n=?-xn приближённых значений х1, … , хn, … корня ?.
    рис 1.4
    Можно заметить, что справедливы равенства ?=?(?) и хn+ 1=?(хn). Из них вытекает, что:
    ?n+ 1= ?-хn+ 1=?(?)-?(хn)
    Но по формуле Лагранжа имеем:
    ?(?)-?(хn)= ? ?(cn)·( ?-xn)= ? ?(cn) ·?n
    где cn - точка лежащая между точками ? и хn. Поэтому:
    ?n+ 1=? ?(cn) ·?n (1.4)
    Из равенства (1.4) вытекает следующий вывод:
    Пусть ? ? корень уравнения x=? (x) - лежит на отрезке [a, b]. Если на этом отрезке выполняется неравенство |? ?(x)|1,
    то процесс итераций расходится.
    Особенно быстро сходится процесс последовательных приближений, если в точке ? производная функции ?(x) обращается в нуль. В этом случае по мере приближения к ?, значение ? ?(x) стремится к нулю. Так как:
    |?n+ 1|=|? ?(cn)|·|?n|
    то сходимость процесса ускоряется по мере приближения к точке ?.
    Однако то же самое можно наблюдать в методе Ньютона, при замене f(x)=0 на имеем: и её производная: в точке ?: f(?)=0 – в методе Ньютона наблюдается ускорение сходимости процесса приближений.
    5. Метод касательных (метод Ньютона)
    Метод касательных, связанный с именем И. Ньютона, является одним из наиболее эффективных численных методов решения уравнений. Идея метода очень проста. Возьмём производную точку x0 и запишем в ней уравнение касательной к графику функции f(x):
    y=f(x0)+ f ?(x) (x-x0) (1.5)
    Графики функции f(x) и её касательной близки около точки касания, поэтому естественно ожидать, что точка x1 пересечения касательной с осью Ox будет расположена недалеко от корня c (рис. 1.5)
    Для определения точки имеем уравнение:
    f(x0)+ f ?(x0) (x1-x0)=0
    таким образом: x1=x0 ? f (x0)/ f ?(x0) (2.5)
    Повторим проделанную процедуру: напишем уравнение касательной к графику функции f(x) при x=x1 и найдём для неё точку пересечения x2 с осью Ox (см. рис.1.5) x2=x1 ? f (x1)/ f ?(x1). Продолжая этот процесс, получим последовательность {xn}, определён- ную с помощью рекуррентной формулы:
    xn+ 1=xn ? f (xn)/ f ?(xn), n=0, 1, 2, … (3.5)
    При исследовании этой последовательности, как и последовательности метода итераций, встают два вопроса:
    Можно ли процесс вычисления чисел xn продолжать неограниченно, т. е. будут ли числа xn принадлежать отрезку [a, b] ?
    Если процесс (3.5) бесконечен, то как ведёт себя последовательность {xn} при n?? ?
    рис. 1.5
    Построение последовательности
    {xn}по методу касательных
    При анализе этих вопросов предположим, что корень x=c является внутренней точкой отрезка [a, b] (a0, | f ??(x)|?M, x?[a, b], (4.5)
    и докажем следующую теорему.
    Теорема о сходимости метода касательных.
    Если функция f(x) удовлетворяет условиям, сформулированным п.1., то найдётся такое ?: 0< ??min(c?a, b?c), что при любом выборе начального приближения на отрезке [c-?, c+?] ? [a, b] существует бесконечная итерационная последовательность (3.5) и эта последовательность сходится к корню c. Доказательство. В силу предположения о дифференцируемости функции f(x) и не равенстве нулю её производной f ?(x) уравнение f(x)=0 эквивалентно на отрезке [a, b] уравне- нию: x=?(x), ?(x)=x? f (x)/ f ?(x) (5.5) так что корень x=c исходного уравнения является одновременно корнем уравнения (5.4). Исследуем возможность отыскания этого корня с помощью итераций. Вычислим производную функции ?(x): (6.5) и оценим полученное выражение. Согласно неравенствам (4.5): (7.5) Для дальнейшей оценки || воспользуемся непрерывностью функции f(x) и равенством её нулю в точке x= с: (8.5) Положим ?=m2/(2M) Тогда в силу (8.5) для данного ? можно указать такое ?: 0ас, так как ас0, a f(x), a > x > b
    В частности, если х0 корень уравнения (1.1): f(x0) = 0, отсюда следует, что
    l(x0) > 0
    C (3.8) и (4.8) получаем:
    l(x) = 0, a > x1 > b
    Таким образом,
    l(x1) < l(x0) (5.8) но линейная функция l(x) строго монотонно возрастает, так как l(b) = f(b) > f(a) = l(a)
    поэтому из (5.8) следует x1 < x0 , заменяя теперь отрезок [a, b] отрезком [x1, b] и замечая, что f(x1) < 0 , аналогично можно доказать, что x1 < x2 < x0, далее по индукции получим: x1 < x2 < … < xn < … < x0, Таким образом, последовательность {xn}, будучи монотонной, сходится. Пусть lim xn = c, при n?? . Переходя к пределу при n?? в равенстве (4.8) получим f(c)=0, т. е. последовательность {xn} сходится к корню уравнения (1.1). Если | f ?(x)|?m>0, a    0,
    , f(a1)<0
    , f(a1)>0
    Если случайно окажется, что точка а3, вычисленная по формуле (1.9), лежит за пределами отрезка [a, b], то на следующем шаге надо вместо этой точки взять ближайший к ней конец этого отрезка (рис. 1.9, б). Оказывается, что сходимость усовершенствованного метода хорд гораздо быстрее, чем у обычного. Именно, если ? – корень уравнения f(x)=0, то:
    |an+ 1|

  9. Детшот Ответить

    (3)
    Метод Зейделя (обобщение метода простой итерации) заключается в следующем: уже полученные значения переменных используются при вычислении остальных искомых переменных на этой итерации. То есть имеет место:
    (4)
    Применяя каждый из методов, необходимо учитывать, что метод Зейделя сходится на порядок быстрее метода простой итерации.
    IV. Выяснить условия сходимости итерационного процесса. При решении практических задач используется следующая теорема: Если матрица А исходной системы имеет диагональное преобладание, то методы простой итерации и Зейделя сходятся.
    V. Указать условия окончания итерационного процесса. В этой роли обычно выступает оценка , где е – наперед заданная точность вычислений.
    Приближенные методы решения систем нелинейных уравнений
    Многие практические задачи при их математическом моделировании сводятся к решению системы нелинейных уравнений. Система n нелинейных уравнений с n неизвестными в общем случае имеет вид
    (1)
    Решением системы уравнений (1) называется n чисел которые при подстановке в (1) обращают все уравнения в нули.
    Задача (1) тесно связана с другой очень часто встречающейся задачей – минимизации функции многих переменных
    (2)
    Эта связь проявляется в том, что каждую из этих задач можно свести к решению другой. Пусть, например, вектор является решением системы (1). Построим функцию
    (3)
    Так как обращает в нуль все уравнения системы (1), то обращает функцию в нуль. Поскольку , то обращает функцию Q в минимум, и этот минимум равен нулю. Справедливо и обратное утверждение. Пусть совокупность чисел обращает функцию в минимум, равный нулю. Тогда каждый член суммы, входящий в (3), обращается в нуль и, следовательно, совокупность является решением системы (1). Таким образом, задача (1) сводится к нахождению минимума (3).
    В свою очередь, для задачи минимизации (2) точка минимума является решением системы нелинейных уравнений.
    Возможность сведения одной задачи к другой не означает, что можно ограничиться рассмотрением только одной из них. Каждая из них является весьма сложной и имеет многочисленные подводные камни, которые проявляются при практической реализации существующих методов их решения. По-видимому, не существует никаких универсальных методов решения этих задач. Установление связи между задачами (1) и (2) удобно тем, что в каждом конкретном случае мы можем использовать ту из них, которая быстрее приводит к цели при располагаемых ресурсах вычислительной техники и математического обеспечения. Трудности при решении систем нелинейных уравнений проявляются в следующем:
    Определение количества корней системы и их отделение проводить достаточно сложно в силу невозможности при больших n использовать простые геометрические соображения.
    Многие надёжные методы нахождения корня одного нелинейного уравнения, имеющие гарантированную сходимость, такие как метод половинного деления или метод хорд и т.д., не допускают обобщения на случай n неизвестных.
    Решение системы (1) ищут, как правило, методом итераций или эффективным по скорости методом Ньютона, сходимость которых возможна только при наличии хорошего начального приближения.
    нахождение хорошего начального приближения для сложной системы (1) является весьма непростым делом и требует, помимо математического анализа системы, привлечение других соображений (физических, инженерных, экономических и др.), связанных с постановкой решаемых задач.
    Замечание 1. никаких универсальных методов преодоления отмеченных трудностей и решения этих задач не существует. Каждый раз приходится, наряду с теоретическими исследованиями системы (1), использовать эвристические соображения и проводить экспериментальные численные исследования. Рассмотрим названные в пункте 3 методы.
    Метод простой итерации.
    Запишем систему (1) в виде, удобном для итераций:
    (4)
    Зададим начальное приближенное решение (индекс в скобках указывает номер итерации), которое будет уточняться в процессе итераций. При этом надо учитывать, что, если метод сходится, то он сходится при любом начальном приближении. Первое приближение вычисляется по формулам:
    ,
    где – нелинейные функции переменных . Затем полученное первое приближение подставляем в правую часть системы (4) и вычисляем второе приближение, и так далее. В общем случае формулы метода простой итерации можно записать в виде:
    (5)
    В роли условия окончания итерационного процесса. обычно выступает оценка (6), где е – наперед заданная точность вычислений.
    Уравнение (4) удобно записать в векторном виде: (7)
    где – вектор-столбец искомого решения, а Ф – вектор-функция
    Итерационный процесс (5) можно также записать в векторном виде
    . (8)
    Условия сходимости итерационного метода (5) (или в векторном виде (8) определяется принципом сжатых соображений: если отображение (7), задаваемое вектор-функцией Ф будет сжатым, то итерационный процесс (8) сходится при условии, что начальное приближение достаточно близко к корню.
    Достаточное условие сходимости метода простой итерации.
    Рассмотрим матрицу Якоби для преобразования (4)
    (9)
    Матрица Якоби (или якобиан) зависит от переменных
    Теорема. если матрица Якоби в точке , которая даёт решение системы (4), и в некоторой её окрестности имеет все собственные значения, по модулю меньше единицы , то метод простой итерации сходится.
    Замечание 2. Для выполнения этого условия достаточно, например, выполнения следующих неравенств для элементов матрицы Якоби
    (10)
    где q – некоторое положительное число, меньшее единицы, т.е. Неравенства (10) должны выполнятся в точке и в некоторой её окрестности.
    Возможно естественное обобщение метода простой итерации (5), аналогичное методу Зейделя для систем линейных уравнений. Оно заключается в том, что переменные , уже полученные на данном итерационном шаге, используются для получение других величин на этом шаге. Соответствующие формулы имеют вид
    (11)
    Если бы оба метода (5) и (11) сходятся, то метод (11) сходится, вообще говоря, быстрее, так как получаемые на каждом шаге итерации новые значения переменных сразу используются в дальнейших вычислениях на этом шаге.
    Метод Ньютона и его модификации.
    Метод Ньютона – метод, который сводит решение системы нелинейных уравнений к последовательному решению систем линейных уравнений для нахождения поправок к предыдущим приближениям.
    Рассмотрим общий вид нелинейной системы (1). Зададим начальное приближение . Будем искать решение системы (1) в виде
    (12)
    Разложим левые части системы (1) в ряд Тейлора в точке , считая величины малыми и в силу этого ограничиваясь только линейными членами в ряде Тейлора. Для функции получим

    =, (i=1,2,…,n) (13)
    Обозначение указывает, что соответствующая частная производная вычисляется в базовой точке , для которой записывается разложение в ряд Тейлора. Поскольку является точным решением системы (1), левые части в уравнениях (13) равны нулю. В результате для неизвестных приращений получим систему линейных уравнений
    (14)
    Матрицей этой системы является якобиан.
    (15)
    Если определитель этой матрицы не равен нулю, то из системы уравнений (14) можно найти неизвестные приращения . Поскольку в разложении Тейлора мы отбросили все члены, кроме линейных, соотношения (12) определяют не точное решение , а уточнение к нулевому приближению
    ,
    или в координатном виде:
    (16).
    Один шаг метода Ньютона заключается в решении системы линейных уравнений (14), все коэффициенты которой и правые части зависят от начального приближения , и в получении уточнённого решения по формулам (16). Приняв теперь полученное первое приближение за начальное и проделав те же операции, которые были сделаны на первом шаге, можно получить следующее приближение к решению Этот итерационный процесс продолжается до тех пор, пока все получаемые приращения становятся малыми по абсолютной величине
    (17)
    Систему линейных уравнений, которую необходимо решать на каждом шаге метода Ньютона, в общем виде можно записать следующим образом:
    (18)
    Индекс k у частных производных указывает, что соответствующая частная производная вычисляется при (для значений искомых переменных на k-ой итерации).
    Решив эту линейную систему и определив из неё величины поправок находим следующее приближение
    (19)
    выражения (18) и (19) полностью определяют один шаг метода Ньютона. Таким образом, метод Ньютона сводит решение систем нелинейных уравнений к многократному решению систем линейных уравнений (18).
    Замечание 3. если метод Ньютона сходится, то сходимость имеет второй порядок, как и в случае уравнения с одной неизвестной.
    Для сходимости метода требуется, чтобы начальное приближение было близко к точному решению, а функции и их первые и вторые производные удовлетворяли некоторым ограничениям. Несмотря на быструю сходимость, метод Ньютона имеет существенный недостаток: на каждом его шаге требуется вычислять n2 частных производных , определяющих коэффициенты при неизвестных в линейной системе (18), то есть якобиан. В то же время в методе простой итерации (5) требуется вычислять всего n функций Чтобы компенсировать этот недостаток метода Ньютона, были предложены различные его упрощения. Идея большинства из этих упрощений заключается в том, чтобы матрицу коэффициентов линейной системы (18) вычислять не на каждом итерационном шаге, а лишь на некоторых из них, считая на остальных шагах все элементы якобиана постоянными, равными их последним вычисленным значениям на том шаге, на котором производится пересчёт всех членов. В простейшем случае якобиан вычисляется один раз, в начальной точке , а затем якобиан остаётся постоянным в течение всего итерационного процесса. Такой метод обычно называется упрощённым методом Ньютона. Матрица коэффициентов линейной системы (18) в этом случае остаётся постоянной, и в процессе итераций изменяются только правые части системы, которые пересчитываются на каждом шаге итераций и решения системы , после нахождения которых происходит пересчёт по формулам (19). Конечно, этот метод сходится медленнее, чем метод Ньютона, но на каждом итерационном шаге требуется гораздо меньше арифметических операций.

  10. Adorarana Ответить

    Приближённые методы решения алгебраического уравнения
    Реферат по курсу численных методов выполнил студент группы РЭ–01-1
    Днепропетровский Национальный Университет
    Радиофизический факультет
    Кафедра физики СВЧ
    Днепропетровск 2002
    1. Численное решение уравнений с одним неизвестным
    В данной работе рассматриваются метода приближённого вычисления действительных корней алгебраического или трансцендентного уравнения
    f(x)=0 (1.1)
    на заданном отрезке [a, b].
    Уравнение называется алгебраическим, если заданная функция есть полином n-ой степени:
    f(x) = P(x) = a0xn + a1xn- 1 + … + an-1 x + an = 0, a0 ? 0
    Требование a0 ? 0 обязательно, так как при невыполнении этого условия данное уравнение будет на порядок ниже.
    Всякое уравнение (1.1) называется трансцендентным, если в нём невозможно явным образом найти неизвестное, а можно лишь приближённо.
    Однако в число алгебраических уравнений можно также включить те уравнения, которое после некоторых преобразований, можно привести к алгебраическому.
    Те методы, которые здесь рассматриваются, применимы, как к алгебраическим уравнениям, так и к трансцендентным.
    Корнем уравнения (1.1) называется такое число ?, где f(?)=0.
    При определении приближённых корней уравнения (1.1) необходимо решить две задачи:
    отделение корней, т. е. определение достаточно малых промежутков, в каждом из которых заключён один и только один корень уравнения (простой и кратный);
    уточнение корней с заданной точностью (верным числом знаков до или после запятой);
    Первую задачу можно решить, разбив данный промежуток на достаточно большое количество промежутков, где бы уравнение имело ровно один корень: на концах промежутков имело значения разных знаков. Там где данное условие не выполняется, те промежутки откинуть.
    Вторая задача решается непосредственно в методах рассмотренных ниже.
    При графическом отделении корней уравнения (1.1) нужно последнее преобразовать к виду:
    ?1(x)=?2(x) (2.1)
    и построить графики функций y1=?1(x), y2=?2(x).
    Действительно, корнями уравнения (1.1)
    f(x) = ?1(x) – ?2(x) = 0
    являются абсциссы точек пересечения этих графиков (и только они).
    Из всех способов, какими можно уравнение (1.1) преобразовать к виду (2.1) выбираем тот, который обеспечивает наиболее простое построение графиков y1=?1(x) и y2=?2(x). В частности можно взять ?2(x) = 0 и тогда придём к построению графика функции (1.1), точки пересечения которого с прямой y2=?2(x)=0, т. е. с осью абсцисс, и есть искомые корни уравнения (1.0).
    Условия, наложенные на функцию f(x) на отрезке [a, b].
    Будем предполагать, что функция f(x) непрерывна на отрезке [a, b] (для метода хорд можно потребовать на интервале) и имеет на этом интервале первую и вторую производные, причём обе они знакопостоянны (в частности отличны от нуля). Будем также предполагать, что функция f(x) принимает на концах отрезка значения разного знака. В силу знакопостоянства первой производной функция f(x) строго монотонна, поэтому при сделанных предположениях уравнение (1.1) имеет в точности один корень на интервале (a, b).
    2. Метод дихотомии
    Этот метод ещё называется методом вилки.
    Нам необходимо найти корень уравнения (1.1) на отрезке [a, b]. Рассмотрим отрезок [x0, x1]: [x0, x1]?[a, b]. Пусть мы нашли такие точки х0, х1, что f (х0) f(х1) ? 0, т. е. на отрезке [х0, х1] лежит не менее одного корня уравнения. Найдём середину отрезка х2=(х0+х1)/2 и вычислим f(х2). Из двух половин отрезка выберем ту, для которой выполняется условие
    f (х2) f(хгран.) ? 0, так как один из корней лежит на этой половине. Затем новый отрезок делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис 1.2).
    рис. 1.2
    Если требуется найти корень с точностью Е, то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2Е. Тогда середина последнего отрезка даст значение корня с требуемой точностью. Дихотомия проста и очень надёжна. К простому корню она сходится для любых непрерывных функций в том числе и не дифференцируемых; при этом она устойчива к ошибкам округления. Скорость сходимости не велика; за одну итерацию точность увеличивается примерно вдвое, т. е. уточнение трёх цифр требует 10 итераций. Зато точность ответа гарантируется.
    Приступим к доказательству того, что если непрерывная функция принимает на концах некоторого отрезка [a, b] значения разных знаков, то методом дихотомии однозначно будет найден корень.
    Предположим для определённости, что функция f(x) принимает на левом конце отрезка [a, b] отрицательное значение, а на правом – положительное:
    f(a) 0.
    Возьмём среднюю точку отрезка [a, b], h=(a+b)/2 и вычислим значение в ней функции f(x). Если f(h)=0, то утверждение теоремы доказано: мы нашли такую точку, где функция обращается в нуль. Если f(h)? 0, тогда из отрезков [a, h] и [h, b] выберем один из них тот, где функция на его концах принимает значения разных знаков. Обозначим его [a1, b1]. По построению: f(a1)0. Затем среднюю точку отрезка [a1, b1] точку h1 и проведём тот же алгоритм нахождения другого отрезка [a2, b2] где бы по построению f(a2)0. Будем продолжать этот процесс. В результате он либо оборвётся на некотором шаге n в силу того, что f(hn)=0, либо будет продолжаться неограниченно. В первом случае вопрос о существовании корня уравнения f(x)=0 решён, поэтому рассмотрим второй случай.
    Неограниченное продолжение процесса даёт последовательность отрезков [a, b], [a1, b1], [a2, b2],… Эти отрезки вложены друг в друга – каждый последующий отрезок принадлежит всем предыдущим:
    an ? an+ 1 < bn+ 1 ? bn (1.2) причём: f(an) 0 Длины отрезков с возрастанием номера n стремятся к нулю: Рассмотрим левые концы отрезков. Согласно (1.2) они образуют монотонно убывающую ограниченную последовательность {an}. Такая последовательность имеет предел, который можно обозначить через c1: Согласно (1.1) и теореме о переходе к пределу в неравенствах имеем: c1 ? bn (2.2) Теперь рассмотрим правые концы отрезков. Они образуют монотонно не возрастающую ограниченную последовательность {bn}, которая тоже имеет предел. Обозначим его через с2: . Согласно неравенству (2.1) пределы с1 и с2 удовлетворяют неравенству с1 ? с2. Итак, an ? с1 < с2 ? bn, и следовательно: с2-с1 ? bn - an=(b-a)/2n. Таким образом, разность с2-с1 меньше любого наперёд заданного положительного числа. Это означает, что с2-с1=0, т. е.: с1=с2=с Найденная точка интересна тем, что она является единственной общей точкой для всех отрезков построенной последовательности Используя непрерывность функции f(x), докажем, что она является корнем уравнения f(x)=0. Мы знаем, что f(an)<0. Согласно определению непрерывности и возможности предельного перехода в неравенствах, имеем: f(c)=lim f(an)?0 (3.2) Аналогично, учитывая, что f(bn)?0, получаем, что: f(c)=lim f(bn) ?0 (4.2) Из (3.2) и (4.2) следует, что f(c)=0. т. е. с – корень уравнения. Процесс построения последовательности вложенных стягивающих отрезков методом вилки (дихотомии) является эффективным вычислительным алгоритмом решения уравнения f(x)=0. На n-ом шаге процесса получаем: an ? c ? bn Это двойное неравенство показывает, что число an определяет корень с недостатком, а число bn с избытком, с ошибкой не превышающей длину отрезка ?n=bn-an=(b-a)/2n. При увеличении n ошибка стремится к нулю по закону геометрической прогрессии со знаменателем q=0.5. Если задана требуемая точность ?>0, то чтобы её достигнуть достаточно сделать число шагов N, не превышающее log2[(b-a)/?]: N>log2[(b-a)/?].
    3. Метод итераций
    Этот метод называется ещё методом последовательных приближений.
    Пусть нам необходимо найти корень уравнения (1.1) на некотором отрезке [a, b].
    Предположим, что уравнение (1.0) можно переписать в виде:
    x=?(x) (1.3)
    Возьмём произвольное значение x0 из области определения функции ?(x) и будет строить последовательность чисел {xn}, определённых с помощью рекуррентной формулы:
    xn +1=?(xn), n=0, 1, 2, … (2.3)
    Последовательность {xn} называется итерационной последовательностью. При её изучении встают два вопроса:
    Можно ли процесс вычисления чисел xn продолжать неограниченно, т. е. будут ли числа xn принадлежать отрезку [a, b] ?
    Если итерационный процесс (2.3) бесконечен, то как ведут себя числа xn при n??
    Исследование этих вопросов показывает, что при определённых ограничениях на функцию ?(x) итерационная последовательность является бесконечной и сходится к корню уравнения (1.3).
    , c=?(c) (3.3)
    Однако для того, чтобы провести это исследование нам нужно ввести новое понятие.
    Говорят, что функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, если существует такая постоянная ?, что для любых x1, x2, принадлежащих отрезку [a, b] имеет место неравенство:
    | f(x1) – f(x2)| ? ?|x1 – x2| (4.3)
    Величину ? в этом случае называют постоянной Липшица.
    Если функция f(x), удовлетворяет на отрезке [a, b] условию Липшица, то она непрерывна на нём. Действительно, пусть x0 – произвольная точка отрезка. Рассмотрим приращение функции f(x) в этой точке:
    ?f=f(x0+?x) – f(x0)
    и оценим его с помощью неравенства (4.3)
    |?f | ? ?|?x|
    Таким образом, , что означает непрерывность функции f(x).
    Условие Липшица имеет простой геометрический смысл. Возьмём не графике функции y=f(x) две произвольные точки M1 и M2 с координатами (x1, f(x1)) и (x2, f(x2)). Напишем уравнение прямой линии, проходящей через эти точки:
    y=f(x1) + k(x-x1)
    где k– тангенс угла наклона прямой у оси Оx и определяется формулой:
    Если функция f(x) удовлетворяет на отрезке [a, b] условию Липшица, то при произвольном выборе точек M1 и M2 имеем |k|??. Таким образом, с геометрической точки зрения условие Липшица означает ограниченность тангенса угла наклона секущих, проведённых через всевозможные пары точек графика функции y=f(x).
    рис 2.3 геометрическая иллюстрация условия Липшица.
    рис 3.3 геометрическая иллюстрация cвязи условия Липшица с предположением о дифференцируемости функции.
    Предположим, что функция f(x) имеет на отрезке [a, b] ограниченную производную:
    | f ?(x)| ? m; тогда она удовлетворяет условию Липшица с постоянной ?=m. Для доказательс- тва этого утверждения воспользуемся формулой конечных приращений Лагранжа:
    f(x2) – f(x1) = f ?(?)(x2-x1) (5.3)
    где x1, x2, – произвольные точки отрезка [a, b] ?, – некоторая точка отрезка [x1, x2]. Возьмём модуль обеих частей равенства (4.3) и заменим в правой части | f ‘(x)| на m. В результате по- лучим неравенство (4.3) с ?=m. Рис.2.3 даёт геометрическую иллюстрацию установленного свойства. Согласно формуле Лагранжа (5.3) каждой секущей графика функции y = f(x) мож- но поставить в соответствие параллельную её касательную. Поэтому наибольший тангенс угла наклона касательных, и его можно оценить той же константой m: |k| ? m.
    Познакомившись с условием Липшица, перейдём к изучению итерационной последовательности, предполагая, что уравнение имеет корень x=c. Существование этого корня можно установить с помощью качественного предварительного исследования уравнения с применением теоремы о существовании корня непрерывной функции.
    Теорема о существовании корня непрерывной функции
    Если функция f(x) непрерывна на отрезке [a, b] и принимает на его концах значения разных знаков, то на этом отрезке существует, по крайней мере, один корень уравнения f(x).
    Теорема о сходимости итерационной последовательности
    Пусть с – корень уравнения (2.3) и пусть функция ?(x) удовлетворяет на некотором отрезке [c-?, c+?] (?>0) условию Липшица с постоянной ?<1. Тогда при любом выборе x0 на отрезке [c-?, c+?] существует бесконечная итерационная последовательность {xn} и эта последовательность сходится к корню x=c, который является единственным решением уравнения (1.3) на отрезке [c-?, c+?].
    Сформулированная теорема имеет очень простой смысл. Будем говорить, что функция ? осуществляет отображение точки x на точку y=?(x). Тогда условие Липшица с постоянной ?<1 означает, что отображение ? является сжимающим: расстояние между точками x1 и x2 больше, чем расстояние между их изображениями y1=?(x1) и y2=?(x2).
    Корень c является неподвижной точкой отображения ?, он преобразуется сам в себя c=?(c). Поэтому каждый шаг в итерационном процессе, сжимая расстояния должен приближать члены последовательности {xn} к неподвижной точке c.
    После таких соображений поясняющих смысл теоремы, перейдём к её доказательству. Возьмём произвольную точку x0 на отрезке [c-?, c+?], она отстоит от точки c не больше чем на ?: |c-x0| ? ?.
    Вычислим x1: x1=?(x0), при этом x1-c =?(x0)-?(c). Разность ?(x0)-?(c) можно оценить с помощью условия Липшица:
    |x1-c| = |?(x0)-?(c)| ? |x0-c| ? ??. (6.3)
    Неравенство (6.3) показывает, что x1 принадлежит отрезку [c-?, c+?] и расположен ближе к точке c, чем x0.
    Продолжим построение итерационной последовательности. Вычислим x2: x2=?(x1), при этом:
    |x2-c| = |?(x1)-?(c)| ? ?|x1-c| ? ?2|x0-c| ? ?2?
    Точка x2 опять принадлежит отрезку [c-?, c+?] и расположена ближе к точке c, чем точка x1, т.е. мы приблизились к c.
    По индукции легко доказать, что последующие итерации также существуют и удовлетворяют неравенствам.
    |xn-c| ? ?n |x0-c| ? ?n? (7.3)
    Отсюда следует, что:
    , т. е.
    Остаётся доказать, что корень x=c (1.3) является единственным решением уравнения на отрезке [c-?, c+?]. Действительно, допустим, что существует ещё один корень x=c1.
    Примем c1 за нулевое приближение и будем строить итерационную последователь- ность (2.3). Тогда с учётом (7.3) получим xn=c1 (n=0, 1, 2, …). С другой стороны, по доказанному , т. е. c1=c. Никаких других решений уравнение на отрезке иметь не может.
    Сходимость итерационной последовательности к корню уравнения (1.3) может быть использована для приближённого определения корня с любой степенью точности. Для этого нужно только провести достаточное количество итераций.
    4. Быстрота сходимости процесса итераций
    Используем теперь производную функции ?(x) для оценки скорости сходимости итераций при решении уравнения х=?(x). Нужно оценить скорость, с которой убывают погрешности ?n=?-xn приближённых значений х1, … , хn, … корня ?.
    рис 1.4
    Можно заметить, что справедливы равенства ?=?(?) и хn+ 1=?(хn). Из них вытекает, что:
    ?n+ 1= ?-хn+ 1=?(?)-?(хn)
    Но по формуле Лагранжа имеем:
    ?(?)-?(хn)= ? ?(cn)·( ?-xn)= ? ?(cn) ·?n
    где cn - точка лежащая между точками ? и хn. Поэтому:
    ?n+ 1=? ?(cn) ·?n (1.4)
    Из равенства (1.4) вытекает следующий вывод:
    Пусть ? – корень уравнения x=? (x) - лежит на отрезке [a, b]. Если на этом отрезке выполняется неравенство |? ?(x)|1,
    то процесс итераций расходится.
    Особенно быстро сходится процесс последовательных приближений, если в точке ? производная функции ?(x) обращается в нуль. В этом случае по мере приближения к ?, значение ? ?(x) стремится к нулю. Так как:
    |?n+ 1|=|? ?(cn)|·|?n|
    то сходимость процесса ускоряется по мере приближения к точке ?.
    Однако то же самое можно наблюдать в методе Ньютона, при замене f(x)=0 на имеем: и её производная: в точке ?: f(?)=0 – в методе Ньютона наблюдается ускорение сходимости процесса приближений.
    5. Метод касательных (метод Ньютона)
    Метод касательных, связанный с именем И. Ньютона, является одним из наиболее эффективных численных методов решения уравнений. Идея метода очень проста. Возьмём производную точку x0 и запишем в ней уравнение касательной к графику функции f(x):
    y=f(x0)+ f ?(x) (x-x0) (1.5)
    Графики функции f(x) и её касательной близки около точки касания, поэтому естественно ожидать, что точка x1 пересечения касательной с осью Ox будет расположена недалеко от корня c (рис. 1.5)
    Для определения точки имеем уравнение:
    f(x0)+ f ?(x0) (x1-x0)=0
    таким образом: x1=x0 – f (x0)/ f ?(x0) (2.5)
    Повторим проделанную процедуру: напишем уравнение касательной к графику функции f(x) при x=x1 и найдём для неё точку пересечения x2 с осью Ox (см. рис.1.5) x2=x1 – f (x1)/ f ?(x1). Продолжая этот процесс, получим последовательность {xn}, определён- ную с помощью рекуррентной формулы:
    xn+ 1=xn – f (xn)/ f ?(xn), n=0, 1, 2, … (3.5)
    рис. 1.5
    Построение последовательности {xn}по методу касательных
    При исследовании этой последовательности, как и последовательности метода итераций, встают два вопроса:
    Можно ли процесс вычисления чисел xn продолжать неограниченно, т. е. будут ли числа xn принадлежать отрезку [a, b] ?
    Если процесс (3.5) бесконечен, то как ведёт себя последовательность {xn} при n?? ?
    При анализе этих вопросов предположим, что корень x=c является внутренней точкой отрезка [a, b] (a0, | f ??(x)|?M, x?[a, b], (4.5)
    и докажем следующую теорему.
    Теорема о сходимости метода касательных.
    Если функция f(x) удовлетворяет условиям, сформулированным п.1., то найдётся такое ?: 0< ??min(c–a, b–c), что при любом выборе начального приближения на отрезке [c-?, c+?] ? [a, b] существует бесконечная итерационная последовательность (3.5) и эта последовательность сходится к корню c. Доказательство. В силу предположения о дифференцируемости функции f(x) и не равенстве нулю её производной f ?(x) уравнение f(x)=0 эквивалентно на отрезке [a, b] уравне- нию: x=?(x), ?(x)=x– f (x)/ f ?(x) (5.5) так что корень x=c исходного уравнения является одновременно корнем уравнения (5.4). Исследуем возможность отыскания этого корня с помощью итераций. Вычислим производную функции ?(x): (6.5) и оценим полученное выражение. Согласно неравенствам (4.5): (7.5) Для дальнейшей оценки | | воспользуемся непрерывностью функции f(x) и равенством её нулю в точке x= с: (8.5) Положим ?=m2/(2M) Тогда в силу (8.5) для данного ? можно указать такое ?: 0ас, так как ас0, a f(x), a > x > b
    В частности, если х0 корень уравнения (1.1): f(x0) = 0, отсюда следует, что
    l(x0) > 0
    C (3.8) и (4.8) получаем:
    l(x) = 0, a > x1 > b
    Таким образом,
    l(x1) < l(x0) (5.8) но линейная функция l(x) строго монотонно возрастает, так как l(b) = f(b) > f(a) = l(a)
    поэтому из (5.8) следует x1 < x0 , заменяя теперь отрезок [a, b] отрезком [x1, b] и замечая, что f(x1) < 0 , аналогично можно доказать, что x1 < x2 < x0, далее по индукции получим: x1 < x2 < … < xn < … < x0, Таким образом, последовательность {xn}, будучи монотонной, сходится. Пусть lim xn = c, при n?? . Переходя к пределу при n?? в равенстве (4.8) получим f(c)=0, т. е. последовательность {xn} сходится к корню уравнения (1.1). Если | f ?(x)|?m>0, a    0
    Если случайно окажется, что точка а3, вычисленная по формуле (1.9), лежит за пределами отрезка [a, b], то на следующем шаге надо вместо этой точки взять ближайший к ней конец этого отрезка (рис. 1.9, б). Оказывается, что сходимость усовершенствованного метода хорд гораздо быстрее, чем у обычного. Именно, если ? – корень уравнения f(x)=0, то:
    |an+ 1|

  11. Mulhala Ответить

    Отделение корней
    Пусть дано уравнение f(x)=0, (1)
    где f(x) определено и непрерывно в некотором конечном или бесконечном интервале a?x?b.
    Всякое значение ?, обращающее функцию f(x) в нуль, то есть такое, что f(?)=0 называется корнем уравнения (1) или нулем функции f(x).
    Число ? называется корнем k-ой кратности, если при x= ? вместе с функцией f(x) обращаются в нуль ее производные до (k-1) порядка включительно
    f(?) = f’(?) = … = fk-1(?) = 0
    Однократный корень называется простым.
    Приближенное нахождение корней уравнения (1) обычно складывается из двух этапов:
    1. Отделение корней, то есть установление интервалов [?i,?i], в которых содержится один корень уравнения (1).
    2. Уточнение приближенных корней, то есть доведение их до заданной точности.
    Для отделения корней полезна след. теорема:
    Теорема 1. Если непрерывная функция f(x) принимает значения разных знаков на концах отрезка [a,b], то есть f(a)f(b)<0, то внутри этого отрезка содержится, по меньшей мере, один корень уравнения f(x)=0, то есть найдется хотя бы одно число ?∈(a,b), такое, что f(?)=0.
    Корень заведомо единственный, если f ‘(x) существует и сохраняет постоянный знак внутри интервала [a,b].
    Доказательство: Пусть для определенности f(a)0. Тогда на интервале [a,b] найдется, по крайней мере, одна точка ? в интервале (?1, ?2) (a< ?1< ?< ?20. (2)
    В силу непрерывности функции для каждого сколь угодно малого ?>0 всегда найдется число ?>0 такое, что при | ? 1- ? 2|< ? выполняется |f1 – f2|0 и f(x) непрерывна, то следовательно существует предел  или f(?)=0 и таким образом, первая часть теоремы доказана.
    Далее, если f ‘(x) сохраняет знак на [a,b] то она будет монотонна, то есть для любых x10) либо f(x1) > f(x2) (если f ‘(x)<0). В силу условия f(a)f(b)<0, монотонности и непрерывности корень будет единственный. Доказательство закончено.
    Рассмотрим графический или табличный способ отделения корней. В заданном интервале [a,b] задается сетка a=x1    , то точность нахождения корня будет равна половине интервала . Нужно еще убедится, является ли найденный корень единственным. Для этого достаточно провести процесс половинного деления, деля интервал [xi, xi+1] на две, четыре и т.д. равных частей и определить знаки функции f(x) в точках деления. При делении мы повышаем точность определения корня.
    Пример №1. Определить корни уравнения f(x) = x3 – 6x +2 = 0
    Решение: Составляем приблизительную схему.
    x
    -?
    -3
    -1
    1
    3
    ?
    f(x)
    –
    –
    +
    +
    –
    +
    +
    Следовательно, уравнение (3.3) имеет три действительных корня лежащих в интервалах (-3,-1), (0,1) и (1,3).
    Для графического решения уравнения (3.3) удобно заменить (3.3) эквивалентным уравнением
    f1(x) = f2(x) или x3 = 6x-2, то есть
    f(x1) = x3,
    f2(x) = 6x-2.
    То значение x=?, при которых f1(? ) = f2(? ) и будет являться корнем уравнения (3.3).

    Пример №2. x*lg(x)=1.
    Решение: ,
    ? ? 2.5.
    Итак, мы выделили интервалы, в которых содержится единственный корень. Рассмотрим теперь методы уточнения корней.
    Прежде чем перейти к методам уточнения корней, дадим определение сходимости последовательности чисел (или сходимости итерационного процесса).
    Определение 1. Если выполняется неравенство
    , (4)
    то говорят, что последовательность {xk} линейно сходится к пределу ?. Здесь α – коэффициент сходимости. Если α > 0, то имеем суперлинейную сходимость.
    Определение 2. Если существует такое r>1 (r=2,3,…), что , (5)
    то последовательность {xk} имеет сходимость порядка r. Здесь c = const.
    Максимум в (4) и (5) берется по всем последовательностям {xk}.
    Пример №3. Отделить корни уравнения f(x), используя графико-аналитический метод. Найти корни уравнения с заданной точностью методами бисекций, Ньютона или простых итераций. Выполнить проверку правильности найденных решений, вычислив невязки.

  12. Turist Ответить

    Введение

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

    Методы численного решения нелинейных уравнений

    Задачу решения я разделил на 3 части:
    Аналитический способ отделения корней
    Численные методы уточнения корней
    Программная реализация вычислительного процесса
    Целью статьи, как я уже называл является разбор и анализ численных методов, по этому в этой статье аналитический способ отделения корней я рассматривать не буду.
    Метод дихотомии или половинного деления.
    Метод дихотомии заключается в последовательном делении отрезка. Выберется промежуток функции — необходимо отделить корни, на пример графическим способом. Получив интервал функции вычисляется его середина и определяется какой отрезок функции, разделенный серединой, больше или меньше нуля, это необходимо для выбора дальнейшего сужения интервала. Процесс сужения продолжается до определенной погрешности, которая задается.
    К плюсам данного метода конечно стоит отнести его простоту. Им легко вычислять как аналитически, так и программно. К минусам нужно отнести затраты на приведенные итерации, по сравнению с методом хорд и касательных на пример.
    Комбинированный метод или метод хорд и касательных
    Методы хорд и метод касательных дают приближения к корню с разных сторон. Совместное использование методов позволяет на каждой итерации находить приближенные значения с недостатком и с избытком, что ускоряет процесс сходимости.
    Идея метода хорд состоит в том чтобы заменить функцию на отрезке хордой, а идея метода касательных или метода Ньютона является замена дуги кривой функции ее касательной. Стоит отметить, что начальное приближение метода хорд определяется тот конец промежутка для которого производная в данной точке умноженная на двойную производную этой же точки меньше нуля, а для метода касательных больше нуля. Процесс сужения так же производится до указанной точности. К плюсам, как уже отмечалось относится быстрота нахождения и меньшая затратность на приведенные итерации
    Метод итераций
    Предварительно необходимо преобразовать уравнение f(x) = 0 к виду x = ?(x).
    В качестве начального приближения x0 выбирается любая точка интервала [a,b].
    Выделяют 2 итерационных метода: лестница и спираль. Если знак производной ?(x) положителен, то используют метод лестницы и наоборот спирали.

    Главным и достаточным условием сходимости итерационного процесса является |?'(x)|<1.
    Достоинство метода. Надежность (обладает самокоррекцией): ошибка в вычислениях, при которой х остается в пределах [a,b ], не влияет на конечный результат, т.к. ошибочное значение можно рассматривать как новое х0.

    Практика. Применение методов.

    Возьмем для примера задачу из области автоматизированного управления — нахождения нулей характеристического уравнения передаточной функции замкнутой системы автоматического управления высокого порядка для оценки ее устойчивости по методу Ляпунова. Сам метод выходит за рамки данного поста, но в прямом методе Ляпунова используется нахождение нулевых корней для выявления устойчивости системы. А для нахождения корней вполне подходят перечисленные методы. Какой метод эффективнее? На этот вопрос сложно ответить не зная конкретной системы к которой это будет применяться. Следует учитывать не только скорость операций, но так же и занимаемые ресурсы.

    Вывод:

    1. Рассмотренные методы уточнения корней одинаково применимы как к алгебраическим, так и к трансцендентным уравнениям.
    2. Операция отделения корней значительно сложнее для трансцендентных уравнений, чем для алгебраических.
    3. Наиболее производительным из рассмотренных является комбинированный метод.
    Мат.часть описанных методов.
    PS: Первый пост и еще не совсем освоился. Помещаю пост в алгоритмы, т.к. блога по выч.мату не нашел.

Добавить ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *