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

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Вятский государственный университет

ФГБОУ ВПО «ВятГУ»

Факультет автоматики и вычислительной техники

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

Отчет

Лабораторная работа №1 по дисциплине

«Моделирование»

Тема:

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

Выполнил студент группы ВМ-32

Умрилов М.В.

Проверил старший преподаватель

Блинова С.Д.

Киров 2012

1. Цель работы и общие требования к её выполнению

Цель работы:

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

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

- освоить приемы работы с электронными таблицами.

Для решения задач используются их математические, алгоритмические, программные модели, конструируемые в среде Microsoft Excel.

2. Нахождение корней уравнения методом деления отрезка пополам

2.1 Постановка и анализ задачи

Дана функция F(x)

F(x) = x²-2, (1)

где х - аргумент.

Требуется на интервале [-2;0] найти один корень уравнения вида

x²-2=0 (2)

Для нахождения корня уравнения (2) использовать метод деления отрезка пополам. Исходными данными является интервал [-2;0] изменения аргумента х, точность результата Е=10^-4 - вещественные числа. Результатом является корень уравнения (2). Поскольку функция (1) является квадратичной, максимальное количество её корней равняется двум, но на исходном интервале находится только один.

Объектом моделирования является метод деления отрезка пополам. Целью моделирования является получение корней уравнения (2) с заданной точностью. Данная цель достигается путём построения алгоритмической модели метода деления отрезка пополам.

2.2 Описание метода деления отрезка пополам

Метод деления отрезка пополам применяется, когда функция F(x) непрерывна и имеет значения разных знаков на концах диапазона изменения аргумента x. За исходное значение корня принимается число с = (a+b)/2, (3)

где a - начало интервала изоляции корня уравнения;

b - конец интервала изоляции корня уравнения.

Далее проверяется условие

F(a)*F(c)0. (4)

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

2.3 Построение алгоритмической модели метода деления отрезка пополам

Алгоритм решения задачи, описанной в 2.1, методом деления отрезка пополам в виде схемы программы приведен на рисунке 1.

Рисунок 1 - Алгоритмическая модель метода деления отрезка пополам

2.4 Результаты решения задачи

На рисунке 2 представлена экранная форма результатов использования алгоритмической модели, представленной на рисунке 1.

Рисунок 2 - Экранная форма результатов нахождения корня уравнения

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

3. Пошаговое решение системы линейных уравнений методом Гаусса

3.1 Постановка и анализ задачи

Дана система линейных уравнений (СЛУ) вида

(5)

где x_j - неизвестные переменные;

j - номер переменной, изменяется от единицы до четырёх.

Требуется найти такие значения переменных x_j с требуемой точностью =10^-5 на множестве всех вещественных чисел, при которых СЛУ (5) будет действительна. Исходными данными являются значения коэффициентов при уравнениях СЛУ (5) - вещественные числа. Выходными данными будет вектор переменных x_j - вещественные числа.

Объектом моделирования является метод Гаусса для решения СЛУ. Целью моделирования является получение значений переменных x_i для системы (5). Цель моделирования достигается путём применения алгоритмической модели метода Гаусса.

3.2 Построение математической модели решения системы линейных уравнений методом Гаусса

Метод Гаусса относится к группе точных методов решения СЛУ и заключается в пошаговом исключении неизвестных до тех пор, пока не будет получено линейное уравнение вида

a_mn^(k)*x_n=a_mn+1^(k), (6)

где a - коэффициенты системы линейных уравнений;

k - номер шага;

m - число уравнений СЛУ, m=4;

n - число переменных СЛУ, n=4.

Уравнение (6) получается последовательно путём деления первого уравнения СЛУ на ведущий коэффициент, находящийся при первой переменной, выражения этой переменной через остальные, подстановку полученного значения в другие уравнения и исключения первого уравнения из СЛУ. Затем данный алгоритм выполняется для новой СЛУ, содержащей (m-1) уравнение и (n-1) переменную до тех пор, пока не будет получено уравнение (6). Коэффициенты при переменных СЛУ на каждом шаге вычисляются по формуле

a_ij^(k)=a_ij^(k-1)-a_ik^(k-1)*(a_kj^(k-1)/a_kk^(k-1)). (7)

где i - номер строки, изменяется от (k+1) до m;

j - номер столбца, изменяется от (k+1) до (n+1).

В результате преобразования исходной СЛУ по алгоритму с помощью формулы (7) получается равнозначная к ней система линейных уравнений, которая для СЛУ типа (5) будет иметь вид

x₁+(a₁₂/a₁₁)x₂+(a₁₃/a₁₁)x₃+(a₁₄/a₁₁)x₄=(a₁₅/a₁₁)

x₂+(a₂₃⁽¹⁾/a₂₂⁽¹⁾)x₃+(a₂₄⁽¹⁾/a₂₂⁽¹⁾)x₄=(a₂₅⁽¹⁾/a₂₂⁽¹⁾) (8)

x₃+(a₃₄⁽²⁾/a₃₃⁽²⁾)x₄=(a₃₅⁽²⁾/a₃₃⁽²⁾)

a₄₄⁽³⁾x₄=a₄₅⁽³⁾ .

После приведения СЛУ к виду (8) проводится этап обратного хода - вычисление неизвестных переменных х, начиная с последней, по формуле

x₄ = a₄₅⁽³⁾/a₄₄⁽³⁾

x₃ = (a₃₅⁽²⁾/a₃₃⁽²⁾) - (a₃₄⁽²⁾/a₃₃⁽²⁾)*x₄ (9)

x₂ = (a₂₅⁽¹⁾/a₂₂⁽¹⁾) - (a₂₄⁽¹⁾/a₂₂⁽¹⁾)*x₄ - (a₂₃⁽¹⁾/a₂₂⁽¹⁾)*x₃

x₁ = (a₁₅/a₁₁) - (a₁₄/a₁₁)*x₄ - (a₁₃/a₁₁)*x₃ - (a₁₂/a₁₁)*x₂

3.3 Построение алгоритмической модели метода Гаусса

Для решения задачи, поставленной в 3.1, необходимо построить алгоритмическую модель метода, описанного в 3.2. Алгоритмическая модель метода Гаусса в виде схемы программы представлена на рисунке 3.

Рисунок 3 - Алгоритмическая модель решения задачи методом Гаусса

уравнение алгоритмический программный модель

3.4 Результаты решения задачи

На рисунке 4 представлена экранная форма результатов работы алгоритмической модели, представленной на рисунке 3.

Рисунок 4 - Экранная форма результатов решения СЛУ

Из рисунка 4 видно, что корнями СЛУ (5), вычисленными по формулам (9) с заданной точностью E являются следующие числа: 0.185714, 0.778571, (-0.63571), 0.457143. Проверка осуществляется подстановкой данных значений в качестве соответствующих переменных в СЛУ (5). Результат проверки показан на рисунке 4.

4. Решение уравнения методом подбора параметров

4.1 Постановка и анализ задачи

Методом подбора параметров найти корни кубического уравнения

x³+0,88х²-0,3999х+0,037638 = 0, (10)

где x -аргумент.

Исходными данными для решения кубического уравнения (10) являются вещественные числа - коэффициенты кубического уравнения: а=1; b= 0.88; c=(-0,3999); свободный член d=0,037638 и число итераций 1000. Исследования производятся на подобранном опытным путём интервале от минус трёх до трёх. Результатом являются вещественные корни уравнения (10) с требуемой точностью Е=10^-4, число которых определяется степенью полинома (10) равной трём, т.е. уравнение имеет не более трёх корней.

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

4.2 Описание процесса решения задачи

При решении задачи, прежде всего, следует получить начальные приближения корней уравнения (10). Для этого необходимо сначала протабулировать значения аргумента х на заданном интервале с некоторым шагом, определяемым экспериментально, а затем для каждого значения таблицы аргументов вычислить значение функции, которой является левая часть уравнения (10). После этого следует найти соседние значения аргумента х, при которых значение функции меняет знак. Таких пар должно быть найдено столько же, сколько корней имеет уравнение. Среднее значение этих величин и следует взять в качестве начального приближения корня. Далее, используя полученные значения приближений корней, следует для каждого из них выполнить команду «Сервис->Подбор параметра» в среде Microsoft Excel, предварительно настроив её параметры: точность результата и наибольшее количество итераций.

4.3 Построение алгоритмической модели процесса решения задачи

Для решения задачи, поставленной в 4.1, необходимо построить алгоритмическую модель процесса, описанного в 4.2. Алгоритмическая модель процесса решения задачи в виде схемы работы системы представлена на рисунке 5.

Рисунок 5 - Алгоритмическая модель процесса решения задачи

4.4 Результаты решения задачи

На рисунке 6 представлена экранная форма результатов эксперимента на компьютерной модели по алгоритму, представленному на рисунке 5.

Рисунок 6 - Экранная форма нахождения корней уравнения

Из рисунка 6 видно, что корнем уравнения (10) с заданной точностью Е является число (-1.23). Это связано с тем, что процесс поиска корней был локализован на участке [-2;2], т.е. если другие корни и есть, то на другом интервале, или необходимо было взять шаг на порядок меньше, для того чтобы не упустить возможное локальное пересечение оси абсцисс. Проверка осуществлялась подстановкой данных значений в уравнение (10). Результаты проверки приведены на рисунке 6.

5. Анализ результатов и выводы по достижению цели работы

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

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

Размещено на Allbest.ru