Расшифровка: Наука в целом (информационные технологии 004)Информационные технологии

Вид материала

Расшифровка

Содержание Ключевые слова Экран оценки творческого уровня работы 1. Методы решения нелинейных уравнений 1.2 Метод простой итерации 1.3 Метод Ньютона (Касательных) 1.4. Метод хорд 1.5 Комбинированный метод (метод хорд и касательных) 1.6. Метод простейших секущих 1.7. Метод секущих Бройдена Выявление наиболее оптимального метода Простых итераций Деления пополам Простых итераций 3. Алгоритм решения уравнения комбинированным методом 4. Программа визуализации процесса нахождения корней нелинейных уравнений методом секущих Бройдена.

Подобный материал:

• Расшифровка : Наука в целом (информационные технологии 004), 98.92kb.
• Расшифровка : Наука в целом (информационные технологии 004), 79.71kb.
• Расшифровка Наука в целом (информационные технологии 004), 95.52kb.
• Название Предмет Направление, 921.62kb.
• Международная конференция «Информационные технологии в образовании и науке», 86.4kb.
• Программа «информатика и икт (информационные и коммуникационные технологии)», 443.93kb.
• Программа «информатика и икт (информационные и коммуникационные технологии)», 827.46kb.
• Программа государственного экзамена по специальности: 230201. 65 «Информационные системы, 450.31kb.
• Информационные технологии образования – новые возможности учащихся и учителей Кузнецова, 124.59kb.
• Межпредметные связи на урок, 42.95kb.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОУВПО «Самарский государственный архитектурно-строительный университет»

Факультет информационных систем и технологий

Кафедра прикладной математики и вычислительной техники


ПОЯСНИТЕЛЬНАЯ ЗАПИСКА К КУРСОВОЙ РАБОТЕ


по дисциплине

ТЕХНОЛОГИЯ ПРОФЕССИОНАЛЬНОЙ ДЕЯТЕЛЬНОСТИ


на тему


«Визуализация процесса нахождения корней нелинейных уравнений методом Бройдена»


5 СЕМЕСТР 3 КУРС


Научный руководитель (ФИО) Бойцев Александр

Преподаватель (ФИО) Филиппов И.С., Шинкарев Г.Г.

Методический руководитель (ФИО) Пиявский С.А.

	Выполнил: студент ГИП-107 Давыдова Евгения
	подпись дата

Оценка преподавателя _______________


Оценка комиссии по результатам защиты_______________


2009 г.

УДК 004.021


Расшифровка:

Наука в целом (информационные технологии - 004)Информационные технологии.

Компьютерные технологии. Теория вычислительных машин и систем

Методы решения задач

Алгоритмы составления программ


Ключевые слова

Алгоритм, Бройдена, метод, решение, уравнения, информационная, система


Реферат

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


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





Аннотация

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

Наиболее простым методом, позволяющим найти корень нелинейного уравнения, является метод половинного деления. Сходимости мала, но к достоинствам метода относятся простота и безусловная сходимость итерационного процесса. Метод Ньютона (Касательных) имеет квадратичную скорость сходимости. Он является одним из оптимальных методов, так же как и комбинированный метод приближения корня уравнения по методу хорд и по методу касательных подходят к значению этого корня с противоположных сторон. Поэтому для быстроты нахождения корня удобно применять оба метода одновременно. Т.к. один метод даёт значение корня с недостатком, а другой – с избытком, то достаточно легко получить заданную степень точности корня.

Решение нелинейных уравнений комбинированным методом возможно только при выполнении следующих условий:

1) ,

2) и сохраняют знак на отрезке ,

Приближения корней находятся:

а) по методу касательных: ,

б) по методу хорд: .


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

В процессе написания программы были реализованы два способа графического представления данного метода (пошаговый и стандартный).

Программа написана в интегрированной среде программирования Delphi 8.0 на языке Pascal. По средствам парсера формул функция преобразовывается в код, затем уравнение решается методом хорд и касательных. После достижения заданной точности выполняется построение графика пошагово и полностью. Парсер был реализован созданием специального класса.

При исследовании сходимости методов решения нелинейных уравнений метод Хорд и касательных оказался наиболее оптимальным из выбранных методов. На втором месте оказался метод Ньютона.

Содержание:


1. Методы решения нелинейных уравнений

1.1. Метод деления отрезка пополам

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

1.3. Метод Ньютона (касательных)

1.4. Метод Хорд

1.5. Комбинированный метод

1.6. Метод простейших секущих

1.7. Метод секущих Бройдена

2. Выявление наиболее оптимального метода

3. Алгоритм решения уравнения комбинированным методом

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

5. Список литературы


1. Методы решения нелинейных уравнений


1.1 Метод деления отрезка пополам


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

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

Итак, алгоритм метода дихотомии:

1. Задать отрезок [a,b] и погрешность .

2. Если f(a) и f(b) имеют одинаковые знаки, выдать сообщение о невозможности отыскания корня и остановиться.



Рис.1. Метод деления отрезка пополам для решения уравнения вида f(х)=0.


3. В противном случае вычислить c=(a+b)/2

4. Если f(a) и f(c) имеют разные знаки, положить b=c, в противном случае a=c.

5. Если длина нового отрезка , то вычислить значение корня c=(a+b)/2 и остановиться, в противном случае перейти к шагу 3.

Так как за N шагов длина отрезка [a, b] сокращается в 2^N раз, то заданная погрешность отыскания корня  будет достигнута за итераций.





Как видно, скорость сходимости мала, но к достоинствам метода относятся простота и безусловная сходимость итерационного процесса. Если отрезок [a, b] содержит больше одного корня (но нечетное число), то всегда будет найден какой-нибудь один.

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


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


При использовании этого метода исходное нелинейное уравнение (1) необходимо переписать в виде


(2)


Обозначим корень этого уравнения C_*. Пусть известно начальное приближение корня . Подставляя это значение в правую часть уравнения (2), получаем новое приближение





и т.д. Для (n+1)- шага получим следующее приближение


(3)


Таким образом, по формуле (3) получаем последовательность С₀, С₁,…,С_n+1, которая стремиться к корню С_* при n. Итерационный процесс прекращается, если результаты двух последовательных итераций близки, т. е. выполняется условие


(4)

Исследуем условие и скорость сходимости числовой последовательности {C _n} при n. Напомним определение скорости сходимости. Последовательность {C_n}, сходящаяся к пределу С_*, имеет скорость сходимости порядка , если при n выполняется условие


(5)


Допустим, что имеет непрерывную производную, тогда погрешность на (n+1)-м итерационном шаге _n+1=C_n+1-C_*=g(C_n)-g(C_*) можно представить в виде ряда


_n+1  C_n+1 – C_* = g(C_*) (C_n-C_*) + g(C_*) _n+


Таким образом, получаем, что при выполнении условия


g(C_*)   (6)


последовательность (3) будет сходиться к корню с линейной скоростью . Условие (6) является условием сходимости метода простой итерации. Очевидно, что успех метода зависит от того, насколько удачно выбрана функция .

Например, для извлечения квадратного корня, т. е. решения уравнения вида x =a², можно положить


x=g₁(x)=a/x (7а)


или

x=g₂(x)=(x+a/x)/2. (7б)


Нетрудно показать, что


g₁^'(C)=1,

g₂^'(C)<1.


Таким образом, первый процесс (7а) вообще не сходится, а второй (7б) сходится при любом начальном приближении С₀ >0.



Рис. 2. Графическая интерпретация метода простых итераций для решения уравнения вида x=g(х).


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


С₀, С₁, …, С_n = C_*

приведено на рисунке 2.


1.3 Метод Ньютона (Касательных)


В литературе этот метод часто называют методом линеаризации. Выбираем начальное приближение С₀. Допустим, что отклонение С₀ от истинного значения корня С_* мало, тогда, разлагая f(C_*) в ряд Тейлора в точке С₀ , получим


f(C_*) = f(C₀) + f (C₀) (C_*-C₀) + (8)


Если f (C₀)  0 , то в (8) можно ограничится линейными по C =C-C₀ членами. Учитывая, что f(C_*)=0, из (9) можно найти следующее приближение для корня


C₁ = C₀ – f (C₀) / f(C₀)


или для (n+1)-го приближения


C_n+1= C _n – f (C _n) / f (C _n) (9)


Для окончания итерационного процесса можно использовать одно из двух условий


C_n+1 – C_n  


или


f(C_n+1)  .


Исследование сходимости метода Ньютона проводится аналогично предыдущему случаю. Самостоятельно получить, что при выполнении условия


f ^''(C)/2f'(C)<1.

метод Ньютона имеет квадратичную скорость сходимости ().



Рис. 3. Графическая интерпретация метода Ньютона для решения уравнения вида f(х)=0.


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


С₀, С₁, …, С_n = C_*


приведено на рисунке 3.

1.4. Метод хорд

Данный способ можно свести к следующему алгоритму:

1. Разделим всю область исследования (Df) отрезки, такие, что внутри каждого отрезка [x₁;x₂] функция монотонная, а на его концах значения функции (x₁) и (x₂) разных знаков. Так как функция (x) непрерывна на отрезке [x₁;x₂], то ее график пересечет ось ОХ в какой либо одной точке между x₁ и x₂.
   

2. Проведем хорду АВ, соединяющую концы кривой y = (x), соответствующие абсциссам x₁ и x₂. Абсцисса a₁ точки пересечения этой хорды с осью ОХ и будет приближенным значением корня. Для разыскания этого приближенного значения напишем уравнение прямой АВ, проходящей через две данные точки A(x₁;(x₁)) и B(x₂; (x₂)), в каноническом виде:
   

;


Учитывая, что y = 0 при x = a₁, выразим из данного уравнения a₁:

3. Чтобы получить более точное значение корня, определяем (а₁). Если на данном отрезке мы имеем (x₁)<0, (x₂)>0 и (a₁)<0, то повторяем тот же прием, применяя формулу (1) к отрезку [a₁;x₂]. Если (x₁)>0, (x₂)<0 и (a₁)>0, то применяем эту формулу к отрезку [x₁;a₁]. Повторяя этот прием несколько раз, мы будем получать все более точные значения корня а₂, а₃ и т.д.
   

1.5 Комбинированный метод (метод хорд и касательных)



Если выполняются условия:


1) ,

2) и сохраняют знак на отрезке ,

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


1.6. Метод простейших секущих


Можно связать задание последовательности () с какой-либо сходящейся к нулю векторной последовательностью, например, с последовательность невязок () или поправок (). Так, полагая где j=1,…n, a k=1,2,…,приходим к простейшему методу секущих — обобщению скалярного метода секущих (5.32):

, (4.1.1)

где



k=1,2,3,….

Этот метод является. двухшаговым и требует задания двух начальных точек и . При п = 1 сходимость метода(4.1.1) имеет порядок . Можно рассчитывать на такую же скорость и в многомерном случае.

К методу секущих так же, как и к методу Ньютона, можно применить пошаговую аппроксимацию обратных матриц на основе метода Шульца. Расчетные формулы этой модификации легко выписать, заменив в совокупности формул ААМН (3.3.1) матрицу на матрицу из (4.1.1)


1.7. Метод секущих Бройдена

В процессе построения методов Ньютона и секущих решения нелинейного скалярного уравнения

(4.4.1)

ф
ункция f(x) в окрестности текущей точки подменяется линейной функцией

(4.4.1а)

Приравнивание к нулю последней, т.е. решение линейного уравнения

,

порождает итерационную формулу

(4.4.2)

для вычисления приближений к корню уравнения (4.4.1).

Если потребовать, чтобы заменяющая функцию f(x) вблизи точки аффинная модель имела в этой точке одинаковую с ней производную, то, дифференцируя (4.4.1а), получаем Значение коэффициента

,

подстановка которого в (4.4.2) приводит к известному методу Ньютона. Если же исходить из того, что наряду с равенством должно иметь место совпадение функций f(x) и в предшествующей точке т.е. из равенства

,

или, в соответствии с (4.4.1а)

, (4.4.3)

то получаем коэффициент

,

превращающий (4.4.2) в известную формулу секущих.

Равенство (4.4.3), переписанное в виде

,

называют соотношением секущих в Оно легко обобщается на n -мерный случай и лежит в основе вывода метода Бройдена. Опишем этот вывод.

В n-мерном векторном пространстве соотношение секущих представляется равенством

, (4.4.4)

где — известные n-мерные векторы, — данное нелинейное отображение, а — некоторая матрица линейного преобразования в . С обозначениями

, (4.4.5)

соотношение секущих в обретает более короткую запись:

(4.4.4а)

Аналогично одномерному случаю, а именно, по аналогии с формулой (4.4.2), будем искать приближения к решению векторного уравнения (2.1а) по формуле

(4.4.6)

Желая, чтобы эта формула обобщала метод секущих (5.32), обратимую n x n-матрицу в ней нужно подобрать так, чтобы она удовлетворяла соотношению секущих (4.4.4). Но это соотношение не определяет однозначно матрицу : глядя на равенство (4.4.4а), легко понять, что при n>1 существует множество матриц , преобразующих заданный n-мерный вектор в другой заданный вектор (отсюда — ясность в понимании того, что могут быть различные обобщения одномерного метода секущих).

При формировании матрицы будем рассуждать следующим образом.

Переходя от имеющейся в точке аффинной модели функции F(x)

(4.4.7)

к такой же модели в точке

(4.4.8)

мы не имеем о матрице линейного преобразования никаких сведений, кроме соотношения секущих (4.4.4). Поэтому исходим из того, что при этом переходе изменения в модели должны быть минимальными. Эти изменения характеризует разность . Вычтем из равенства (4.4.8) определяющее равенство (4.4.7) и преобразуем результат, привлекая соотношение секущих (4.4.4). Имеем:



Представим вектор в виде линейной комбинации фиксированного вектора определенного в (4.4.5), и некоторого вектора t, ему ортогонального:

,

Подстановкой этого представления вектора в разность получаем другой ее вид

(4.4.9)

Анализируя выражение (4.4.9), замечаем, что первое слагаемое в нем не может быть изменено, поскольку



- фиксированный вектор при фиксированном k. Поэтому минимальному изменению аффинной модели будет отвечать случай, когда второе слагаемое в (4.4.9) будет нуль-вектором при Iвсяких векторах t, ортогональных векторам , т.е. следует находить из условия

. (4.4.10)

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

.

Таким образом, приходим к так называемой формуле пересчета С. Бройдена (1965 г.)

(4.4.11)

которая позволяет простыми вычислениями перейти от старой матрицы к новой такой, чтобы выполнялось соотношение секущих (4.4.4а) в новой точке и при этом изменения в аффинной модели (4.4.7) были минимальны

Совокупность формул (4.4.6), (4.4.11) вместе с обозначениями (4.4.5) называют методом секущих Бройдена или просто методом Бройдена решения систем нелинейных числовых уравнений.

Хотя в методах секущих обычным является задание двух начальных векторов ( и ), для метода Бройдена характерно другое начало итерационного процесса. Здесь нужно задать один начальный вектор , начальную матрицу и далее в цикле по k = 0,1,2,... последовательно выполнять следующие операции:

1. решить линейную систему
   

(4.4.12)

относительно вектора :

2. найти векторы и :
   

, ; (4.4.13)

3. сделать проверку на останов (например, с помощью проверки на малость величин и/или и если нужная точность не достигнута, вычислить новую матрицу по формуле пересчета (см. (4.4.11))
   

(4.4.14)

В качестве матрицы , требуемой равенством (4.4.12) для запуска итерационного процесса Бройдена, чаще всего берут матрицу Якоби или какую-нибудь ее аппроксимацию. При этом получаемые далее пересчетом (4.4.14) матрицы , ,... не всегда можно считать близкими к соответствующим матрицам Якоби , ,... (что может иногда сыграть полезную роль при вырождении матриц ). Но, в то же время, показывается, что при определенных требованиях к матрицам Якоби матрицы обладают «свойством ограниченного ухудшения», означающим, что если и происходит увеличение с увеличением номера итерации k, то достаточно медленно. С помощью этого свойства доказываются утверждения о линейной сходимости () к х*

при достаточной близости к х* и к а в тех предположениях, при которых можно доказать квадратичную сходимость метода Ньютона (3.1.2), — о сверхлинейной сходимости последовательности приближений по методу Бройдена.

Как и в случаях применения других методов решения нелинейных систем, проверка выполнимости каких-то условий сходимости итерационного процесса Бройдена весьма затруднительна.

Формуле пересчета (4.4.14) в итерационном процессе можно придать чуть более простой вид.

Так как, в силу (4.4.12) и (4.4.13),

,

а

,

то из формулы (4.4.14) получаем формально эквивалентную ей формулу пересчета

, (4.4.14а)

которую можно использовать вместо (4.4.14) в совокупности с формулой (4.4.6) или с (4.4.12), (4.4.13) (без вычисления вектора ). Такое преобразование итерационного процесса Бройдена несколько сокращает объем вычислений (на одно матрично-векторное умножение на каждой итерации). Не следует, правда, забывать, что при замене формулы (4.4.14) формулой (4.4.14а) может измениться ситуация с вычислительной устойчивостью метода; к счастью, это случается здесь крайне редко, а именно, в тех случаях, когда для получения решения с нужной точностью требуется много итераций по методу Бройдена, т.е. когда и применять его не стоит.

2. Выявление наиболее оптимального метода
   

Для выявления наиболее оптимального метода решения нелинейных уравнений были решены 10 различных уравнений предложенными методами.

В таблицу было выписано количество шагов сходимости для каждого метода:

Методы	1	2	3	4	5	6	7	8	9	10
Бройдена	4	6	3	5	3	4	5	5	3	4
Комбинированный	5	4	5	4	5	3	5	4	5	3
Хорд	6	7	6	6	6	7	9	7	8	7
Ньютона	5	6	6	6	5	7	6	8	6	5
Простых итераций	7	7	8	7	6	7	9	8	7	8
Деления пополам	8	9	7	8	8	8	11	9	10	7

По результатам таблицы была составлена гистограмма в которой можно заметить, что Комбинированный метод и метод Бройдена имеют самую быструю сходимость:




Для наиболее четкого результата были подсчитаны и сравнены средние значения:

Методы	Среднее
Бройдена	4,2
Комбинированный	4,3
Хорд	6,9
Ньютона	6
Простых итераций	7,4
Деления пополам	8,5

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

3. Алгоритм решения уравнения комбинированным методом

1. Вычислить значения функции и .
   
2. Проверить выполнение условия . Если условие не выполняется, то неправильно выбран отрезок .
   
3. Найти производные и .
   
4. Проверить постоянство знака производных на отрезке . Если нет постоянства знака, то неверно выбран отрезок .
   
5. Для метода касательных выбирается за тот из концов отрезка , в котором выполняется условие , т.е. и одного знака.
   
6. Приближения корней находятся:
   

а) по методу касательных: ,

б) по методу хорд: .

7. Вычисляется первое приближение корня: .
   
8. Проверяется выполнение условия: , где - заданная точность.
   

Если условие не выполняется, то нужно продолжить применение метода по схеме 1-8.

В этом случае отрезок изоляции корня сужается и имеет вид . Приближённые значения корня находятся по формулам:

и .

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


4. Программа визуализации процесса нахождения корней нелинейных уравнений методом секущих Бройдена.





Библиографический список


1. Методические указания к выполнению лабораторных работ по дисциплине «Методы оптимизации и принятия решений» / С.А.Пиявский; Самарск. гос. арх.-строит. ун-т./ Самара, 2007.

2. «Учебник по Delphy 7», Семенов П.А. ,Москва, 2007 г.

3. Приближённое решение алгебраических и трансцендентных уравнений [Электронный ресурс] // Режим доступа: ссылка скрыта.

4. «Методы решения нелинейных уравнений», Попов А.В. , Москва, 2008 г.

5. Графические возможности среды программирования Borland Delphi 7.0 // Режим доступа: ссылка скрыта.

6. Применение парсера формул // Режим доступа: ссылка скрыта.

7. «Статистический анализ линейных величин», Васильев Л.П., Зимин В.Н. , Москва 2009 г.

8. Решение систем нелинейных уравнений методом секущих // Режим доступа: ссылка скрыта.