Метод итераций последовательного приближения реферат

Обновлено: 19.05.2024

Сложность заключается в том, что с увеличением количества исходных данных (при переходе от к к к + 1) быстро увеличивается необходимое число проверок. Метод полного перебора применим в тех случаях, когда искомое решение У = ДХ) принадлежит некоторой конечной области и может быть найдена простая функция quality (У) для проверки правильности (или качества) выбранного решения. Тогда задача Р… Читать ещё >

Метод последовательных приближений ( реферат , курсовая , диплом , контрольная )

Основной проблемой является построение задачи R по исходной задаче Р, доказательство факта сходимости процесса к искомому решению и обеспечение достаточно высокой скорости сходимости.

Решение обратной задачи Иногда обратная задача, т. е. задача, соответствующая функции/'(У) = X, решается значительно более просто, чем исходная задача. Тогда имеющийся алгоритм решения обратной задачи R иногда можно использовать для построения алгоритма решения прямой задачи Р.

Метод полного перебора

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

Сложность заключается в том, что с увеличением количества исходных данных (при переходе от к к к + 1) быстро увеличивается необходимое число проверок. Метод полного перебора применим в тех случаях, когда искомое решение У = ДХ) принадлежит некоторой конечной области и может быть найдена простая функция quality (У) для проверки правильности (или качества) выбранного решения. Тогда задача Р вычисления функции/ заменяется многократным решением задачи R вычисления функции quality (столько раз, сколько элементов имеется в области решений). Причем в общем случае просмотреть нужно всю область, и порядок, в котором просматриваются элементы, не важен.

Метод реализует стратегию постепенного уточнения значения корня.

Постановка задачи. Дано нелинейное уравнение (3.1). Корень отделен x* Î [a;b]. Требуется уточнить корень с точностью ε.

Уравнение ( 3.1) преобразуем к эквивалентному виду x=φ(x), (3.7)

Что можно сделать всегда и притом множеством способов.

Выберем начальное приближение x0Î [a;b].

Вычислим новые приближения:

Xi=φ(xi-1) , i=1,2,… где i − номер итерации. (3.8)

Последовательное вычисление значений xi по формуле (3.8) называется итерационным процессом метода простых итераций, а сама формула - формулой итерационного процесса метода.

Если , то итерационный процесс Сходящийся .

Условие сходимости (3.9)

Точное решение x* получить невозможно, так как требуется Бесконечный Итерационный процесс.

Можно получить Приближенное Решение, прервав итерационный (3.8) при достижении условия

Где ε - заданная точность; i - номер последней итерации.

В большинстве случаев условие завершения итерационного процесса (3.10) обеспечивает близость значения xi к точному решению:

Рассмотрим геометрическую иллюстрацию метода простых итераций.

Уравнение (3.7) представим на графике в виде двух функций: y1 = x и y2= φ(x).

Возможные случаи взаимного расположения графиков функций, и соответственно, видов итерационного процесса показаны на рис. 3.7 – 3.10.

Рис. 3.7 Итерационный процесс для случая 0 1 xÎ[a, b].

Рис. 3.10 Итерационный процесс для случая £ - 1 xÎ[a, b].

Из анализа графиков следует, что скорость сходимости растет при уменьшении значения

Метод достаточно прост, обобщается на системы уравнений, устойчив к погрешности округления (она не накапливается).

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

Рис 3.11. Алгоритм решения нелинейного уравнения методом
простых итераций:

Основной проблемой применения метода является обеспечение сходимости итерационного процесса: нужно найти такое эквивалентное преобразование (3.1) в (3.7), чтобы обеспечивалось условие сходимости (3.9) .

Простейшие эквивалентные преобразования, например:

F(x) = 0 => x+f(x) = x, т. е. φ(x) = x + f(x)

Или выразить явно x из (3.1)

F(x) = 0 => x - φ(x) = 0 => x = φ(x)

Не гарантируют сходимость.

Рекомендуется следующий способ получения формулы Сходящегося итерационного процесса.

Если это не так, переписать уравнение (3.1) в виде

Умножить обе части уравнения на и к обеим частям прибавить x:

Константу l вычислить по формуле:

Такое значение λ гарантирует сходящийся итерационный процесс по формуле

Xi = xi+1− λ f(x) (3.12)

Где i=1,2,… - номер итерации, x0Î[a, b] – начальное приближение.

Методом простых итераций уточнить корень уравнения x3=1-2 x с точностью ε=0,001. Корень отделен ранее (см. пример 3.1), x* Î [0;1].

Сначала нужно получить формулу сходящегося итерационного процесса.

Из уравнения выразим явно x:

Проверим условия сходимости для полученной формулы:

Условие сходимости не соблюдается, полученная формула не позволит уточнить корень.

Воспользуемся описанным выше способом получения формулы итерационного процесса (формулы 3.11, 3.12).

, , для всех x Î [0;1].

Наибольшее значение принимает при x = 1, т. е.

Формула Сходящегося итерационного процесса

Уточним корень с помощью данной формулы.

Выберем начальное приближение на [0;1], например x0=0,5 (середина отрезка).

Вычислим первое приближение

Проверим условие завершения итерационного процесса

Расчет следует продолжить.

X6 = 0,453917 − ответ, т. к.

Проверим полученное значение, подставив в исходное уравнение:

Значение f(x) близко к 0 с точностью, близкой к ε, следовательно, корень уточнен правильно.

Процесс проектирования ведется в условиях информационного дефицита, который проявляется в следующем:

• невозможность заранее точно указать условия работы проектируемого объекта, не зная его конкретного вида и устройства (исходные данные зависят от вида конечного решения);
• выявление в процессе проектирования противоречивых исходных данных, то есть невозможность достижения технического решения при первоначально предложенных данных, оказавшихся взаимоисключающими;
• появление в процессе проектирования необходимости учёта дополнительных условий и ограничений, которые ранее считались несущественными;
• перераспределение по степени важности показателей качества, так как может выясниться, что показатель, ранее считавшийся второстепенным, очень важен (и наоборот).

Такая неопределенность устраняется посредством выполнения итерационных процедур:

Число циклов итераций зависит от степени неопределенности начальной постановки задачи, её сложности, опыта и квалификации проектировщика, требуемой точности решения. В процессе приближений возможно не только уточнение, но и отказ от первоначальных предположений.

Хотя итерационный метод решения задачи часто связан с большими затратами времени и средств (и чем больше циклов итераций, тем больше затраты), ещё ни одна техническая система (а также законопроект, книга и т. д.) не была создана с первого раза. С другой стороны, желательно не увлекаться итерациями при выполнении дорогих или продолжительных проектных работ.

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

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

Если не известно, что и как делать (нет идей, данных, определенности и т. п.), возьмите в качестве исходного решения любое известное (идею, схему, данные,…) или предположите какое-нибудь (но желательно разумное) решение задачи. Проанализировав выбранное решение на соответствие условиям задачи, станет видно, что вас в нём не устраивает и в каком направлении его надо улучшать.

Метод декомпозиции

Пример иерархической структуры (блок-схема)

Любую исследуемую систему можно рассматривать как сложную, состоящую из отдельных взаимосвязанных подсистем, которые, в свою очередь, также могут быть расчленены на части. Такой процесс расчленения системы называется декомпозицией. В качестве систем могут выступать не только материальные объекты, но и процессы, явления и понятия.

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

Упрощенное графическое представление иерархической структуры может быть изображено в виде ветвящейся блок-схемы, на подобие представленной на рисунке.

Здесь на нулевом уровне располагается исходная система С₁ , на следующих уровнях — её подсистемы (число уровней и количество подсистем, показанных на рисунке, выбрано произвольно). С целью получения более полного представления о системе и её связях в структуру включают надсистему и составляющие её части (системы нулевого уровня, например, вторая система С₂).

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

Методы декомпозиции и последовательных приближений очень распространены, причем часто те, кто применяет их, даже не воспринимают их как методы. Очень эффективным является совместное использование этих методов.

Метод контрольных вопросов

Суть метода контрольных вопросов заключается в ответе на специально подобранные по содержанию и определенным образом расставленные наводящие вопросы.

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

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

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

• Почему так или такое? А как ещё иначе? (применительно к назначению узлов и деталей, их частей и форм, к последовательности выполнения действий и т. д.).
• Зачем это нужно?
• Что произойдет, если этого не будет?
• И другие.

Применительно к проектированию варианты метода были предложены А.Осборном (1964 г., США) и Т.Эйлоартом (1969 г., США).

Метод синектики

На основе метода мозговой атаки разработан ряд других методов, среди которых наиболее известен метод синектики. Его существенной чертой является значительное задействование возможностей подсознания.

ГОСТ

Одной из целей этого метода состоит в нахождении приближенных решений уравнений. Одним из таких методов является метод простой итерации.

Метод простой итерации

Метод простой итерации - один из самых простейших численных методов для решения уравнений.

Идея метода простой итерации.

Пусть нам необходимо решить уравнение $f\left(x\right)=0$.

Вначале для его решения приведем его к эквивалентному уравнению вида

Рассмотрим пример такого приведения:

Привести уравнение $-x^2=0$ к виду $x=\varphi (x)$.

Решение.

Здесь есть три способа такого преобразования:

После этого каким-либо образом выбирается начальное приближение $x_0$, вычисляется значение $\varphi (x_0)$ и находится уточненное значение $x_1=\varphi (x_0)$. Следующее уточненное значение будет находиться как $x_2=\varphi (x_1)$ и т.д. Каждый такой шаг называется шагом итерации.

Сформулируем и докажем следующую теорему:

Функция $\varphi (x)$ определена и дифференцируема на отрезке $[a,b]$ и $\varphi (x)\in [a,b]$. Тогда, если \textbar $'\left(x\right)|

Процесс итерации $x_n=\varphi (x_)$ сходится независимо от начального положения $x_0$;

$<\mathop_ x_n\ >=X$ -- единственный корень уравнения $x=\varphi (x)$ на отрезке $[a,b]$.

Доказательство.

\item Так как $X=\varphi (x)$ и $x_n=\varphi (x_)$, то

\[x_n-X=\varphi \left(x_\right)-\varphi \left(x\right)=\left(\varphi \left(x_\right)-\varphi \left(x\right)\right)\frac=\] \[=\frac<\varphi \left(x_\right)-\varphi \left(x\right)>\cdot x_-x\]

По теореме о среднем, получаем

Пусть $M=max |'\left(x\right)|$, тогда $|x_n-X|\le M|x_-x|$. Также$|x_-X|\le M|x_-x|$. Но тогда получим

\[\left|x_n-X\right|\le M\left|x_-x\right|\le M^2\left|x_-x\right|и\ т.д.\]

То есть получим, что

Следовательно, для того чтобы метод сходился нужно, чтобы $M=max |'\left(x\right)|$ было меньше единицы, значит $\left|'\left(x\right)\right|

Рассмотрим $x_n=\varphi (x_)$ и $x_=\varphi (x_n)$.

\[x_-x_n=\varphi \left(x_n\right)-\varphi (x_)\]

По теореме о среднем $x_-x_n=f'\left(x_n\right)(x_n-x_)$.

Так как $\left|'\left(x\right)\right|\le q

Рассмотрим теперь $f\left(x\right)=x-\varphi \left(x\right)$, $f^<'\left(x\right)>=1-^<'\left(x\right)>\ge 1-q$. Значит, $\left|x_n-\varphi \left(x_n\right)\right|=\left|f\left(x_n\right)-f\left(X\right)\right|=\left|x_n-X\right|\left|f'\left(x_n\right)\right|\ge \left(1-q\right)|x_n-X|$. Следовательно, $|x_n-X|\le \frac<\left|x_n-\varphi \left(x_n\right)\right|>\le \frac<|x_-x_n|>$.

Из двух полученных неравенств, имеем

Пусть $|x_n-X|\le \varepsilon $, тогда $x_0,x_1,\dots ,x_n$ нужно вычислять до тех пор, пока не выполнится неравенство $|x_n-x_|\le \frac$, тогда получим, что $X=x_n\pm \varepsilon $. Отсюда следует, что $X$ корень уравнения $x=\varphi (x)$, то есть $X=\varphi (X)$.

Предположим, что это уравнение имеет еще один корень $X'=\varphi \left(X'\right)$. Отсюда $X'-X=\varphi \left(X'\right)-\varphi \left(X\right)$, тогда $\left(X'-X\right)\left|1-'\left(C\right)\right|=0$. Значит $X'=X$.

Готовые работы на аналогичную тему

Теорема доказана.

Из теоремы будет вытекать погрешность метода простой итерации. Она определяется следующей формулой:

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

Рассмотрим теперь на примере использование метода простой итерации.

Решить уравнение $sinx-x^2=0$ с точностью до $\varepsilon =0,001$.

Решение.

Вначале приведем уравнение к виду $x=\varphi (x)$.

Очевидно, что корень уравнения находит на отрезке $\left[\frac<\pi >,\frac<\pi >\right]$.

Найдем $\varphi (x)$:

Она возрастает на отрезке $\left[\frac<\pi >,\frac<\pi >\right]$, следовательно принимает максимальное значение, при $x=\frac<\pi >$. $\left|'\left(x\right)\right|\le \left|'\left(\frac<\pi >\right)\right|\approx 0,312$.

Условие выполняется, $q \[|x_n-x_|\le \varepsilon \]

Это неравенство выполнится на 5 шаге.

Приведем таблицу промежуточных решений, взяв за $x_0$ единицу:

Ответ: приближенное значение с заданной точностью -- $0,8765$.

Изучение способов решения алгебраических и трансцендентных уравнений. Описание назначения, расчет алгоритма, построение блок-схемы метода решения алгебраических уравнений методом итераций. Разработка программы для определения интервалов уравнений функции.

Рубрика	Программирование, компьютеры и кибернетика
Вид	контрольная работа
Язык	русский
Дата добавления	04.12.2013
Размер файла	203,8 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

алгоритм итерация интервал алгебраическое уравнение

Решение алгебраических и трансцендентных уравнений

Алгоритм метода итераций

Блок-схема метода итераций

Идеи и достижения математики используются в практической деятельности человека. До недавнего времени главные усилия математиков были направлены на разработку теорий. Строгое математическое обновление ранее выработанных методов - расширение объектов, к которым эти методы можно применить.

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

неполное соответствие математической модели реальному физическому процессу;

погрешность исходных данных;

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

Решение алгебраических и трансцендентных уравнений

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

Если в левой части уравнения стоит функция вида: , то уравнение (1) называется алгебраическим уравнением n - ной степени, и оно имеет n корней. Коэффициенты а_к (к = 0, 1, 2, …, n) могут быть любыми числами.

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

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

Метод итераций

(метод последовательных приближений)

Рассмотрим уравнение (1), где функция непрерывна и дифференцируема на некотором отрезке [а, в]. Перепишем уравнение в виде (2) , т.е. . Пусть каким-либо образом найдено грубое значение корня х₀. Подставив его в правую часть уравнения (2) получим число , подставив х₁ в (2) найдем и т.д. (3). Допустим, что получившаяся числовая последовательность имеет предел, т.е. . Переходя к пределу выражения (3) . Получаем , т.е. с - корень уравнения (2).

Вопрос о сходимости последовательности решает теорема.

Пусть функция непрерывна и дифференцируема на некотором отрезке [а, в] и пусть:

все ее значения тоже € [а, в], € [а, в];

на [а, в], q - некоторое число.

Тогда последовательность, задаваемая соотношением (3) сходится при любых х₀ € [а, в].

Рассмотрим два последовательных приближения и , тогда по теореме Лагранжа, которая звучит: , где с € (х_п, х_п-1).

Допустим, , т.е. . Подставляя вместо п последовательно значения п = 1, 2, 3, …, п получим:

перемножая неравенства получим (4).

Рассмотрим два ряда:

Ряд В сходится как геометрическая прогрессия, если 0 ! (е)(с - с)

где е € (х_п, х_п-1) (по теореме Лагранжа). (с - с) ! (1 - ц ! (е)) =0.

Так как 1 - ц ! (е)?0 (ц ! (е) 0, т.е. за отрезок отделения берем [0, 1].

уточним корень. Запишем уравнение в виде (*).

Проверим условие теоремы: 1) все значения € [0, 1]: , условие выполняется. 2).

, отсюда получим , т.е. , поэтому за начальную точку берем х₀ = 0, подставим это значение в (*) и найдем , и т.д. Заполним в виде таблицы:

Читайте также:

  
• Понятие тнк типы тнк индекс транснационализации тнк роль тнк в мировой экономике реферат
  
• Атомы в мирных целях реферат
  
• Первая лекарская школа монастырские и первые гражданские больницы богадельни на руси реферат
  
• Реферат о болезни 2 класс
  
• Реферат на тему фетоплацентарная недостаточность