Как заполнить симплекс таблицу. Решение производственной задачи табличным симплекс-методом. Вопросы для самоконтроля
Дана система n алгебраических уравнений сn неизвестными:
Эту систему можно записать в матричном
виде:
,
;
;
.
где A - квадратная матрица коэффициентов,X - вектор-столбец неизвестных,B - вектор-столбец свободных членов.
Численные методы решения систем линейных уравнений делятся на прямые и итерационные. Первые используют конечные соотношения для вычисления неизвестных. Пример - метод Гаусса. Вторые основаны на последовательных приближениях. Примеры - метод простой итерации и метод Зейделя.
Метод Гаусса
Метод основан на приведении матрицы системы к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы. Сначала с помощью первого уравнения исключается x 1 из всех последующих уравнений. Затем с помощью второго уравнения исключаетсяx 2 из последующих и т.д. Этот процесс называется прямым ходом метода Гаусса и продолжается до тех пор, пока в левой части последнегоn -го уравнения не останется лишь один член с неизвестнымx n . В результате прямого хода система принимает вид:
(2)
Обратный ход метода Гаусса состоит в последовательном вычислении искомых неизвестных, начиная с x n и кончаяx 1 .
Метод простой итерации и метод Зейделя
Решение систем линейных уравнений с помощью итерационных методов сводится к следующему. Задается начальное приближение вектора неизвестных, в качестве которого обычно выбирается нулевой вектор:
.
Затем организуется циклический вычислительный процесс каждый цикл которого представляет собой одну итерацию. В результате каждой итерации получается новое значение вектора неизвестных. Итерационный процесс заканчивается, если для каждой i -й компоненты вектора неизвестных будет выполнено условие
(3)
где k - номер итерации, - заданная точность.
Недостатком итерационных методов является жесткое условие сходимости. Для сходимости метода необходимо и достаточно, чтобы в матрице A абсолютные значения всех диагональных элементов были больше суммы модулей всех остальных элементов в соответствующей строке:
(4)
Если условие сходимости выполнено, то можно организовать итерационный процесс, записав систему (1) в приведенном виде. При этом слагаемые, стоящие на главной диагонали нормируются и остаются слева от знака равенства, а остальные переносятся в правую часть. Для метода простой итерации приведенная система уравнений имеет вид:
(5)
Отличие метода Зейделя от метода простой итерации заключается в том, что при вычислении очередного приближения вектора неизвестных используются уже уточненные значения на этом же шаге итерации. Это обеспечивает более быструю сходимость метода Зейделя. Приведенная система уравнений имеет вид:
(6)
3.4. Реализация в пакете Excel
В качестве примера рассмотрим систему уравнений:
Данная система удовлетворяет условию сходимости и может быть решена как прямыми, так и итерационными методами. Последовательность действий (рис.7):
Оформить заголовок в строке 1 «Численные методы решения систем линейных уравнений».
В области D3:H6 ввести исходные данные, как показано на рисунке.
Ввести в ячейку F8 текст заголовка «Метод Гаусса» (выравнивание по центру).
Скопировать исходные данные E4:H6 в областьB10:E12. Это - исходные данные для прямого хода метода Гаусса. Обозначим соответствующие строкиA1,A2 иA3.
Подготовить место для первого прохода, обозначив в области G10:G12 названия строкB1,B2 иB3.
Ввести в ячейку H10 формулу «=B10/$B$10». Скопировать эту формулу на ячейкиI10:K10. Это - нормировка на коэффициентa 11 .
Ввести в ячейку H11 формулу «=B11-H10*$B$11». Скопировать эту формулу на ячейкиI11:K11.
Ввести в ячейку H12 формулу «=B12-H10*$B$12». Скопировать эту формулу на ячейкиI12:K12.
Подготовить место для второго прохода, обозначив в области A14:A16 названия строкC1,C2 иC3.
Ввести в ячейку B14 формулу «=H10». Скопировать эту формулу на ячейкиC14:E14.
Ввести в ячейку B15 формулу «=H11/$I$11». Скопировать эту формулу на ячейкиC15:E15.
12. Ввести в ячейку В16 формулу «=Н12-В15*$I$12». Скопировать эту формулу на ячейки С16:Е16.
13. Подготовить место для третьего прохода, обозначив в области G14:G16 названия строк D1, D2 и D3.
14. Ввести в ячейку H14 формулу «=В14». Скопировать эту формулу на ячейки I14:К14.
15. Ввести в ячейку H15 формулу «=В15». Скопировать эту формулу на ячейки I15:К15.
16. Ввести в ячейку Н16 формулу «=B16/$D$16». Скопировать эту формулу на ячейки I16:К16.
17. Подготовить место для обратного хода метода Гаусса, введя в ячейки В18, E18 и H18 соответствующие тексты «х3=», «х2=» и «х1=».
18. Ввести в ячейку С18 формулу «=К16». Получим значение переменной х 3.
19. Ввести в ячейку F18 формулу «=К15-J15*К16». Получим значение переменнойх 2.
20.Ввести в ячейку I18 формулу «=K10-I10*F18-J10*C18». Получим значение переменнойх 1.
21. Ввести в ячейку F21 текст заголовка «Метод простой итерации» (выравнивание по центру).
22. Ввести в ячейку J21 текст «е=» (выравнивание по правому краю).
23. Ввести в ячейку К21 значение точности е (0,0001).
24. Обозначить в области А23:А25 названия переменных.
25. В области В23:В25 задать начальные значения переменных (нули).
26. Ввести в ячейку С23 формулу «=($H$4-$F$4*B24-$G$4*B25)/$E$4». Получим значение переменной х 1 на первой итерации.
27. Ввести в ячейку С24 формулу «=($H$5-$E$5*B23-$G$5*B25)/$F$5». Получим значение переменной х 2 на первой итерации.
28. Ввести в ячейку С25 формулу «=($H$6-$E$6*B23-$F$6*B24)/$G$6». Получим значение переменной х 3 на первой итерации.
29. Ввести в ячейку С26 формулу «=ЕСЛИ(АВS(С23-В23)>$К$21;" "; ЕСЛИ(АВS(С24-В24)>$К$21;" ";ЕСЛИ(АВS(С25-В25)>$К$21;" "; ""корни")))». Это - проверка на достижение заданной точности (при этом печатается сообщение «корни»).
30. Выделить диапазон С23:С26 и скопировать его до столбца К, используя прием протаскивания. При появлении в строке 26 сообщения «корни» соответствующий столбец будет содержать приближенные значения переменных х 1,x 2, x 3, которые являются решением системы уравнений с заданной точностью.
31. В области А27:К42 построить диаграмму, показывающую процесс приближения значений переменных х 1,х 2,x 3 к решению системы. Диаграмма строится в режиме «График», где по оси абсцисс откладывается номер итерации.
32. Ввести в ячейку F43 текст заголовка «Метод Зейделя» (выравнивание по центру).
33. Ввести в ячейку J43 текст «е=» (выравнивание по правому краю).
34. Ввести в ячейку К43 значение точности е(0,0001).
35. Обозначить в области А45:А47 названия переменных.
36. В области В45:В47 задать начальные значения переменных (нули).
37.Ввести в ячейку С45 формулу «=($H$4-$F$4*B46-$G$4*B47)/$E$4». Получим значение переменной х 1 на первой итерации.
38.Ввести в ячейку С46 формулу «=($H$5-$E$5*C45-$G$5*B47)/$F$5». Получим значение переменной х 2 на первой итерации.
39. Ввести в ячейку С47 формулу «=($H$6-$E$6*C45-$F$6*C46)/$G$6». Получим значение переменной x 3 ,на первой итерации.
40. Ввести в ячейку С48 формулу «=ЕСЛИ(АВ5(С45-В45)>$К$43;" "; ЕСЛИ(АВS(С46-В46)>$К$43;" ";ЕСЛИ{АВS(С47-В47)>$К$43;" ";"корни")))».
41. Выделить диапазон С45:С48 и скопировать его до столбца К, используя прием протаскивания. При появлении в строке 26 сообщения «корни» соответствующий столбец будет содержать приближенные значения переменных х 1,х 2,x 3, которые являются решением системы уравнений с заданной точностью. Видно, что метод Зейделя сходится быстрее, чем метод простой итерации, то есть заданная точность здесь достигается за меньшее число итераций.
42. В области А49:К62 построить диаграмму, показывающую процесс приближения значений переменных х1, х2, x3 к решению системы. Диаграмма строится в режиме «График», где по оси абсцисс откладывается номер итерации.
Нахождение корней уравнений
Графический способ нахождения корней заключается в построении графика функции f(x) на отрезке . Точка пересечения графика функции с осью абсцисс дает приближенное значение корня уравнения.
Найденные таким образом приближенные значения корней позволяют выделить отрезки , на которых при необходимости можно выполнить уточнение корней.
При нахождении корней расчетным путем для непрерывных функций f(x) руководствуются следующими соображениями:
– если на концах отрезка функция имеет разные знаки, то между точками a и b на оси абсцисс имеется нечетное число корней;
– если же функция имеет одинаковые знаки на концах интервала, то между a и b имеется четное число корней или их совсем нет;
– если на концах отрезка функция имеет разные знаки и либо первая производная, либо вторая производная не меняют знаки на этом отрезке, то уравнение имеет единственный корень на отрезке .
Найдем все действительные корни уравнения x 5 –4x–2=0 на отрезке [–2,2]. Создадим электронную таблицу.
Таблица 1
В таблице 2 получены результаты расчета.
Таблица 2
Аналогично находится решение на интервалах [-2,-1], [-1,0].
Уточнение корней уравнения
С использованием режима «Поиск решений»
Для данного выше уравнения следует уточнить с погрешностью Е=0,001 все корни уравнения x 5 –4x–2=0.
Для уточнения корней на интервале [-2,-1] составим электронную таблицу.
Таблица 3
Запускаем режим «Поиск решения» в меню «Сервис». Выполняем команды режима. Режим показа отобразит найденные корни. Аналогично уточняем корни на других интервалах.
Уточнение корней уравнений
С использованием режима «Итерации»
Метод простых итераций имеет два режима «Вручную» и «Автоматически». Для запуска режима «Итерации» в меню «Сервис» открывают вкладку «Параметры». Далее следуют командам режима. На вкладке «Вычисления» можно выбрать режим автоматический или ручной.
Решение систем уравнений
Решение систем уравнений в Excel проводится методом обратных матриц. Решить систему уравнений:
Создадим электронную таблицу.
Таблица 4
| A | B | C | D | E | |
| Решение системы уравнений. | |||||
| Ax=b | |||||
| Исходная матрица А | Правая часть b | ||||
| -8 | |||||
| -3 | |||||
| -2 | -2 | ||||
| Обратная матрица (1/А) | Вектор решения x=(1/A)/b | ||||
| =МОБР(А6:С8) | =МОБР(А6:С8) | =МОБР(А6:С8) | =МУМНОЖ(А11:С13;Е6:Е8) | ||
| =МОБР(А6:С8) | =МОБР(А6:С8) | =МОБР(А6:С8) | =МУМНОЖ(А11:С13;Е6:Е8) | ||
| =МОБР(А6:С8) | =МОБР(А6:С8) | =МОБР(А6:С8) | =МУМНОЖ(А11:С13;Е6:Е8) |
Функция МОБР возвращает массив значений, который вставляется сразу в целый столбец ячеек.
В таблице 5 представлены результаты расчета.
Таблица 5
| A | B | C | D | E | |
| Решение системы уравнений. | |||||
| Ax=b | |||||
| Исходная матрица А | Правая часть b | ||||
| -8 | |||||
| -3 | |||||
| -2 | -2 | ||||
| Обратная матрица (1/А) | Вектор решения x=(1/A)/b | ||||
| -0,149 | 0,054 | -0,230 | |||
| 0,054 | 0,162 | -0,189 | |||
| -0,122 | 0,135 | -0,824 |
Список использованных литературных источников
1. Турчак Л.И. Основы численных методов: Учеб. пособие для вузов/ ред. В.В. Щенников.–М.: Наука, 1987.–320с.
2. Банди Б. Методы оптимизации. Вводный курс.–М.: Радио и связь, 1988.–128с.
3. Евсеев А.М., Николаева Л.С. Математическое моделирование химических равновесий.–М.: Изд-во Моск. ун-та, 1988.–192с.
4. Безденежных А.А. Инженерные методы составления уравнений скоростей реакций и расчета кинетических констант.–Л.: Химия, 1973.–256с.
5. Степанова Н.Ф., Ерлыкина М.Е., Филиппов Г.Г. Методы линейной алгебры в физической химии.–М.: Изд-во Моск. ун-та, 1976.–359с.
6. Бахвалов Н.С. и др. Численные методы в задачах и упражнениях: Учеб. пособие для вузов/ Бахвалов Н.С., Лапин А.В., Чижонков Е.В. - М.: Высш. шк., 2000.-190с. - (Высшая математика/ Садовничий В.А.)
7. Применение вычислительной математики в химической и физической кинетике, под ред. Л.С. Полак, М.: Наука, 1969, 279 стр.
8. Алгоритмизация расчетов в химической технологии Б.А. Жидков, А.Г. Бондарь
9. Вычислительные методы для инженеров-химиков. Х.Розенброк, С.Стори
10. Орвис В.Д. Excel для ученых, инженеров и студентов. – Киев: Юниор, 1999.
11. Ю.Ю. Тарасевич Численные методы на Mathcade – Астраханский гос.пед.ун-т: Астрахань, 2000.
Напомню, что циклическая ссылка появляется, если в ячейку Excel введена формула, содержащая ссылку на саму эту ячейку (напрямую или через цепочку других ссылок). Например (рис. 1), в ячейке С2 находится формула, ссылающаяся на саму ячейку С2.
Но!.. Не всегда циклическая ссылка является бедствием. Циклическую ссылку можно использовать для решения уравнений итерационным способом. Для начала нужно позволить Excel`ю вести вычисления, даже при наличии циклической ссылки. В обычном режиме Excel, обнаружив циклическую ссылку, выдаст сообщение об ошибке, и потребует ее устранения. В обычном режиме Excel не может провести вычисления, так как циклическая ссылка порождает бесконечный цикл вычислений. Можно, либо устранить циклическую ссылку, либо допустить вычисления по формуле с циклической ссылкой, но ограничив число повторений цикла. Для реализации второй возможности щелкните на кнопке «Office» (в левом верхнем углу), а затем на «Параметры Excel» (рис. 2).
Скачать заметку в формате , примеры в формате
Рис. 2. Параметры Excel
В открывшемся окне «Параметры Excel» перейдите на вкладку Формулы и отметьте «Включить итеративные вычисления» (рис. 3). Помните, что эта опция включается для приложения Excel в целом (а не для одного файла), и будет действовать, пока вы ее не отключите.
Рис. 3. Включить итеративные вычисления
На этой же вкладе, можно выбрать, как будут вестись вычисления: автоматически или вручную. При автоматическом вычислении Excel сразу рассчитает конечный результат, при вычислениях, вручную, можно будет наблюдать результат каждой итерации (простым нажатием F9 запуская каждый новый цикл вычисления).
Решим уравнение третьей степени: х 3 – 4х 2 – 4х + 5 = 0 (рис. 4). Для решения этого уравнения (и любого другого уравнения совершенно произвольного вида) понадобится всего одна ячейка Excel.
Рис. 4. График функции f(x)
Для решения уравнения нам понадобится рекуррентная формула (то есть, формула, выражающая каждый член последовательности через один или несколько предыдущих членов):
(1) x = x – f(x)/f’(x), где
х – переменная;
f(x) – функция, задающая уравнение, корни которого мы ищем; f(x) = х 3 – 4х 2 – 4х + 5
f’(x) – производная нашей функции f(x); f’(x) = 3х 2 – 8х – 4; производные основных элементарных функций можно посмотреть .
Если вы заинтересовались, откуда взялась формула (1), можете почитать, например, .
Итоговая рекуррентная формула имеет вид:
(2) х = x – (х 3 – 4х 2 – 4х + 5)/(3х 2 – 8х – 4)
Выберем любую ячейку на листе Excel (рис. 5; в нашем примере это ячейка G19), присвоим ей имя х , и введем в нее формулу:
(3) =x-(x^3-4*x^2-4x+5)/(3*x^2-8*x-4)
Можно вместо х использовать адрес ячейки… но согласитесь, что имя х , смотрится привлекательнее; следующую формулу я ввел в ячейку G20:
(4) =G20-(G20^3-4*G20^2-4*G20+5)/(3*G20^2-8*G20-4)
Рис. 5. Рекуррентная формула: (а) для поименованной ячейки; (б) для обычного адреса ячейки
Как только мы введем формулу и нажмем Enter, в ячейке сразу же появится ответ – значение 0,77. Это значение соответствует одному из корней уравнения, а именно второму (см. график функции f(x) на рис. 4). Поскольку начальное приближение не задавалось, итерационный вычислительный процесс начинался со значения, по умолчанию хранимого в ячейке х и равного нулю. Как же получить остальные корни уравнения?
Для изменения стартового значения, с которого рекуррентная формула начинает свои итерации, предлагается использовать функцию ЕСЛИ:
(5) =ЕСЛИ(x=0;-5;x-(x^3-4*x^2-4*x+5)/(3*x^2-8*x-4))
Здесь значение «-5» – начальное значение для рекуррентной формулы. Изменяя его, можно выйти на все корни уравнения.
Министерство общего образования
Российской федерации
Уральский государственный технический университет-УПИ
филиал в г.Краснотурьинске
Кафедра вычислительной техники
Курсовая работа
По численным методам
Решение линейных уравнений методом простой итерации
c помощью программы Microsoft Excel
Руководитель Кузьмина Н.В.
Студент Нигматзянов Т.Р.
Группа М-177Т
Тема: «Нахождение с заданной точностью корня уравнения F(x)=0 на промежутке методом простой итерации».
Контрольный пример: 0,25-х+sinx=0
Условия задачи: для заданной функции F(x) на интервале найти корень уравнения F(x)=0 методом простой итерации.
Корень вычислить дважды(с помощью автоматического и ручного расчета).
Предусмотреть построение графика функции на заданном интервале.
Введение 4
1.Теоретическая часть 5
2.Описание хода работы 7
3.Входные и выходные данные 8
Заключение 9
Приложение 10
Библиографический список 12
Введение.
В ходе данной работы мне необходимо ознакомиться с различными методами решения уравнения и найти корень нелинейного уравнения 0,25-х+sin(x)=0 численным методом – методом простой итерации. Для проверки правильности нахождения корня необходимо решить уравнение графически,найти приближенное значение и сравнить его с полученным результатом.
1.Теоретичесакя часть.
Метод простой итерации.
Итерационный процесс состоит в последовательном уточнении начального приближения х0 (корня уравнения). Каждый такой шаг называется итерацией.
Для использования этого метода исходное нелинейное уравнение записывается в виде: х=j(х), т.е. выделяется х; j(х) – непрерывна и дифференцируема на интервале (а; в). Обычно это можно сделать несколькими способами:
Например:
arcsin(2x+1)-x 2 =0 (f(x)=0)
Способ 1.
arcsin(2x+1)=x 2
sin(arcsin(2x+1))=sin(x 2)
x=0.5(sinx 2 -1) (x=j(x))
Способ 2.
x=x+arcsin(2x+1)-x 2 (x=j(x))
Способ 3.
x 2 =arcsin(2x+1)
x= (x=j(x)),знак берется в зависимости от интервала [а;b].
Преобразование должно быть таким, чтобы ½j(x)<1½ для всех принадлежащих интервалу .В таком случае процесс итерации сходится.
Пусть известно начальное приближение корня x=c 0 .Подставляя это значение в правую часть уравнения x=j(x),получаем новое приближение корня:c=j(c 0).Далее, подставляя каждый раз новое значение корня в x=j(x),получаем последовательность значений
c n =j(c n-1) n=1,2,3,…
Процесс итераций следует
продолжать до тех пор,пока для двух последовательных приближений не будет
выполнено условие: ½c n -c n -1 ½ Решать уравнения численными
методами можно с помощью языков программирования, но программа Excel дает возможность справиться сданной задачей более простым
способом. Программа Excel
реализует метод простой итерации двумя способами с помощью ручного расчета и с
автоматическим контролем точности. j с 0 с 2
с 4 с 6 с 8 корень
с 9 с 7 с 5 с 3
с 1 2.Описание хода работы. 1.
Запустил МЕ. 2.
Построил график функции y=x и y=0,25+sin(x) на
отрезке с шагом 0,1 назвал лист «График». 3.
Выбрал команду Сервис
®
Параметры. 4.
Ввел в ячейку А1 строку «Решение
уравнения x=0,25+sin(x) методом простой итерации». 5.
Ввел в ячейку А3 текст «Начальное
значение»,в ячейку А4 текст «Начальный флаг»,в ячейку В3 значение 0,5 ,в ячейку
В4 слово ИСТИНА. 6.
Присвоил ячейкам В3 и В4 имя
«нач_зн» и «нач». 7.
В ячейку А6 ввел y=x,и в
ячейку А7 y=0,25+sin(x).В ячейку В6 формулу: 8.
В ячейку А9 ввел слово
Погрешность. 9.
В ячейку В9 ввел формулу: =В7-В6. 10.
С помощью команды Формат-Ячейки
(вкладка
Число
) преобразовал ячейку В9 в экспоненциальный формат с двумя
цифрами после запятой. 11.
Затем организовал вторую
циклическую ссылку-для подсчета количества ите-раций.В ячейку А11 ввел текст
«Количество итераций». 12.
В ячейку В11 ввел формулу:
=ЕСЛИ(нач;0;В12+1). 13.
В ячейку В12 ввел =В11. 14.
Для выполнения расчета установил
табличный курсор в ячейку В4 и нажал клавишу F9(Вычислить)
для запуска решения задачи. 15.
Изменил значение начального флага
на ЛОЖЬ,и снова нажал F9.При каждом нажатии F9 выполняется
одна итерация и вычисляется следующее приближен-ное значение х. 16.
Нажимал клавишу F9 до
тех пор, пока значение х не достигло необходимой точности. 17.
Перешел на другой лист. 18.
Повторил пункты с 4 по 7,только в
ячейку В4 ввел значение ЛОЖЬ. 19.
Выбрал команду Сервис
®
Параметры
(вкладка
Вычисления
).Установил зна-чение поля Предельное число
итераций
равным 100,относительную погреш-ность равной 0,0000001.Включил
ркжим Автоматически
. 3.Входные и выходные данные. Начальный флаг ЛОЖЬ. Функция
y=0,25-x+sin(x) Границы
интервала Точность
вычисления при ручном расчете 0,001 при автоматическом Выходные: 1.
Ручной расчет: 2.
Автоматический расчет: 3.
Решение уравнения графическим
способом: Заключение. В ходе данной курсовой работы я ознакомился с
различными методами решения уравнений: ·
Графическим методом ·
Численным методом Но так как
большинство численных методов решения уравнений являются итерационными, то я на
практике использовал этот метод. Нашел с заданной точностью корень уравнения
0,25-x+sin(x)=0 на промежутке методом простой итерации. Приложение. 1.Ручной расчет. 2.Автоматический расчет. 3.Решение уравнения 0.25-x-sin(x)=0
графическим способом. Библиографический список. 1.
Волков Е.А. «Числовые методы». 2.
Самарский А.А. «Введение в
числовые методы». 3.
Игалеткин И.И. «Числовые методы».
у у=х
(с 0)
Рис. График итерационного процесса
Открыл вкладку Вычисления
.
Включил режим Вручную
.
Отключил флажок Пересчет перед сохранением
. Сделал значение поля Пре-дельное
число итераций
равным 1,относительную погрешность 0,001.
В ячейке В6 будет выполняться проверка,равна ли истина значению ячейки
«нач».Если это так,х будет установлено равным начальному значению, в противоположном
случае равным ячейке В7,т.е. 0,25+синуса х.В ячейке В7 выч-исляется 0,25-синуса
ячейки В6,и тем организуется циклическая ссылка.
=ЕСЛИ(нач;нач_зн;В7).
В ячейку В7 формулу: y=0,25+sin(B6).
При автоматическом расчете:
Начальное значение 0,5
число итераций 37
корень уравнения 1,17123
число итераций 100
корень уравнения 1,17123
корень уравнения 1,17
·
Аналитическим методом
