Теория ОС | Безопасность | Сетевые ОС | TCP/IP | Windows 2000 | Лок. сети | Интернет | Защита

| Топология сети | Выч. сети
Корпоративные ИС | Учебник КС | C++ | Архитектура ЭВМ | Local Area Network | Брандмауэры | Паскаль | Базы данных | SQL Создание нового файла рисунка

 

Метод секущих Приближённое нахождение корней уравнений

В качестве функции $ {\lambda}(x)$ берут любую постоянную $ {\lambda}_0$, знак которой совпадает со знаком производной $ f'(x)$ в окрестности $ E$ (и, в частности, на отрезке, соединяющем $ x_0$ и $ x^*$). Постоянная $ {\lambda}_0$ не зависит также и от номера шага $ i$. Тогда формула итераций оказывается очень проста:

$\displaystyle x_{i+1}=x_i-{\lambda}_0f(x_i),$

и на каждой итерации нужно один раз вычислить значение функции $ f(x)$.

Выясним смысл этой формулы, а также смысл условия о совпадении знаков $ f'$ и $ {\lambda}_0$. Рассмотрим прямую, проходящую через точку $ (x_i;f(x_0))$ на графике $ y=f(x)$ с угловым коэффициентом $ \mathop{\rm tg}\nolimits {\alpha}=\dfrac{1}{{\lambda}_0}$. Тогда уравнением этой прямой будет

$\displaystyle y=f(x_i)+\dfrac{1}{{\lambda}_0}(x-x_i).$
Скалярное и векторное поле Математика решение задач

Найдём точку пересечения этой прямой с осью $ Ox$ из уравнения

$\displaystyle f(x_i)+\dfrac{1}{{\lambda}_0}(x-x_i)=0,$

откуда $ x=x_i-{\lambda}_0f(x_i)=x_{i+1}$. Следовательно, эта прямая пересекает ось $ Ox$ как раз в точке следующего приближения. Тем самым получаем следующую геометрическую интерпретацию последовательных приближений. Начиная с точки $ x_0$, через соответствующие точки графика $ y=f(x)$ проводятся секущие с угловым коэффициентом $ k=\dfrac{1}{{\lambda}_0}$ того же знака, что производная $ f'(x_0)$. (Заметим, что, во-первых, значение производной вычислять не обязательно, достаточно лишь знать, убывает функция $ f(x)$ или возрастает; во-вторых, что прямые, проводимые при разных $ x_i$, имеют один и тот же угловой коэффициент $ k$ и, следовательно, параллельны друг другу.) В качестве следующего приближения к корню берётся точка пересечения построенной прямой с осью $ Ox$.

Рис.9.11.Последовательные итерации метода секущих

На чертеже слева изображены итерации при $ f'(x)>0$, в случае $ k=\dfrac{1}{{\lambda}_0}<f'(x_0)$ и в случае $ k=\dfrac{1}{{\lambda}_0}>f'(x_0)$. Мы видим, что в первом случае меняющаяся точка $ x_i$ уже на первом шаге "перепрыгивает" по другую сторону от корня $ x^*$, и итерации начинают приближаться к корню с другой стороны. Во втором случае последовательные точки $ x_i$ приближаются к корню, оставаясь всё время с одной стороны от него. (Исследуйте сами, как выглядит процесс в случае $ f'(x)<0$, то есть когда функция $ f(x)$ убывает.)

Достаточное условие сходимости, которое нам даёт теорема 9.3, таково:

$\displaystyle \vert{\varphi}'(x)\vert=\vert 1-{\lambda}_0f'(x)\vert\leqslant {\gamma}<1.$

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

$\displaystyle -{\gamma}+1\leqslant {\lambda}_0f'(x)\leqslant {\gamma}+1,$

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

$\displaystyle {\lambda}_0f'(x)>0,$

так как $ -{\gamma}+1>0$ (тем самым проясняется смысл выбора знака числа $ {\lambda}_0$), а во-вторых, когда $ {\lambda}_0f'(x)<2$ при всех $ x$ на всём рассматриваемом отрезке, окружающем корень. Это второе неравенство заведомо выполнено, если

$\displaystyle \vert k\vert=\dfrac{1}{\vert{\lambda}_0\vert}>\dfrac{M_1}{2},$

где $ M_1=\max\limits_{x}\vert f'(x)\vert$. Таким образом, угловой коэффициент $ k$ не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка $ x_1$ может выскочить из рассматриваемой окрестности корня $ x^*$, и сходимость итераций к корню может быть нарушена.

Основные обозначения и определения Функции и их графики

 

Пример 1.4 При сдаче пальто в гардероб каждому сданному пальто $ p$ соответствует ровно один выданный номерок $ n$. Таким образом, между множеством $ P$ сданных пальто и множеством выданных номерков $ N'$ ($ N'$-- это подмножество множества $ N$ всех номерков в гардеробе) устанавливается биекция $ f: p\mapsto n$ ($ p\in P$, $ n\in N'$).

Определение 1.4 Если $ f:A\to B$-- биекция, то отображение, сопоставляющее каждому $ y\in B$ тот элемент $ x\in A$, который переходит в этот самый $ y$ при отображении $ f$, называется обратным отображением (или обратной функцией) к отображению $ f$ и обозначается $ f^{-1}$. Таким образом, $ f^{-1}:B\to A$, и $ f^{-1}(y)=x$ тогда и только тогда, когда $ f(x)=y$ ($ x\in A$, $ y\in B$).

Пример 1.5 В условиях примера 1.4 отображение $ f:P\to N'$-- биекция. При выдаче пальто из гардероба по каждому из выданных номерков $ n\in N'$ находят соответствующее номерку пальто $ p\in P$. Соответствие $ g:N'\to P$, $ n\mapsto p$ ($ n\in N'$, $ p\in P$)-- это обратная функция к функции $ f:P\to N'$, $ p\mapsto n$, то есть $ g=f^{-1}$.

Классификация операционных систем Виртуальная память Реализация многозадачности
Системы безопасности Операционная система Linux Введение в компьютерные сети Принципы построения вычислительных систем Базовые технологии локальной сетиСредства анализа Процедуры и функции Pascal Язык запросов SQL Программирование на СИ Брандмауэры Протоколы TCP/IP Файловые системы Драйверы устройств