- •Численные методы решения задач строительства
- •Часть 1
- •Предисловие
- •В ведение
- •Общие сведения о вычислительном эксперименте и математическом моделировании
- •Численные методы.
- •Погрешности вычислений
- •Понятия точности, устойчивости и сходимости при численном решении
- •1.1. Матрицы и векторы.
- •1.2. Матрицы специального вида
- •Глава 1 Основные понятия матричного исчисления
- •1.3. Действия над матрицами
- •1.4. Нормы матрицы и вектора
- •1.5. Функции ms Excel для операций над матрицами
- •Контрольные вопросы
- •Г лава 2. Численные методы решения нелинейных уравнений
- •2.1. Первый этап. Отделение корней
- •Второй этап. Этап уточнения корня
- •Iteration (итерация)- повторение, ре-зультат повторного применения какой-либо математической операции.
- •Метод половинного деления (бисекции)
- •Метод хорд
- •Метод Ньютона (метод касательных)
- •Модифицированный метод Ньютона
- •Реализация численных методов решения нелинейных уравнений средствами приложения ms Excel
- •Последовательность действий:
- •2.3.1. Решение нелинейных уравнений с использованием надстройки «Подбор параметра»
- •Последовательность действий
- •Контрольные вопросы
- •3.2. Прямые методы решения систем линейных алгебраических уравнений
- •3.2.1. Метод Гаусса
- •3.2.2. Метод прогонки
- •Алгоритм метода прогонки
- •3.3. Итерационные методы решения систем линейных алгебраических уравнений
- •3.3.1. Метод Якоби (простых итераций)
- •3.3.2. Метод Гаусса – Зейделя.
- •3.3.3. Условия сходимости итерационного процесса
- •3.5. Устойчивость решения слау относительно исходных данных (или обусловленность задач и вычислений)
- •3.6. Примеры решения слау с использованием электронных таблиц ms Excel
- •3.6.1. Реализация метода Гаусса
- •Последовательность действий
- •Прямой ход метода Гаусса.
- •3.6.2. Решение слау с помощью надстройки «Поиск решения»
- •Последовательность действий:
- •3.6.3. Реализация метода Якоби средствами приложения ms Excel
- •Последовательность действий
- •3.6.4. Реализация метода прогонки средствами приложения Excel
- •Последовательность действий
- •Контрольные вопросы
- •Г лава 4. Численное интегрирование
- •Алгоритм метода половинного шага.
- •4.1. Квадратурные формулы прямоугольников
- •4.2. Квадратурная формула трапеций
- •4.3. Квадратурная формула Симпсона
- •4.4. Реализация методов численного интегрирования средствами приложения Ms Excel
- •Последовательность действий:
- •Контрольные вопросы
- •Г лава 5. Аппроксимация
- •5.1. Задачи аппроксимации
- •5.2. Интерполирование функций
- •5.2.1. Постановка задачи интерполирования
- •5.2.2. Интерполяционная формула Лагранжа
- •5.3. Среднеквадратичное приближение функций
- •5.3.1. Постановка задачи
- •5.3.2. Метод наименьших квадратов
- •5.3.3. Линейная эмпирическая формула (линейная регрессия)
- •5.3.4. Коэффициент корреляции
- •5.3.5. Квадратичное (параболическое) приближение
- •5.3.6. Эмпирические формулы с двумя параметрами (метод выравнивания)
- •5.4. Решение задач аппроксимации с помощью электронных таблиц Excel
- •5.4.1. Построение уравнений регрессии методом наименьших квадратов с использованием надстройки «Поиск решения»
- •Последовательность действий
- •5.4.2. Построение линейной эмпирической формулы с использованием встроенных функций линейн и тенденция
- •Последовательность действий
- •Последовательность действий
- •Контрольные вопросы
- •Глава 6. Численные методы оптимизации
- •6.1. Общие сведения
- •6.1.1. Математическая модель задачи оптимизации
- •6.1.2. Классификация задач математического программирования
- •6.2. Постановка задачи оптимального проектирования
- •6.3. Задачи линейного программирования
- •6.3.1. Общая постановка задачи
- •6.3.2. Геометрический смысл системы линейных неравенств
- •Случай n проектных параметров.
- •6.3.3. Геометрический метод решения задач линейного программирования
- •Последовательность действий:
- •6.3.4. Симплекс-метод решения задач линейного программирования
- •Примеры задач линейного программирования в сфере проектирования и управления строительным производством
- •6.4.1. Задача об оптимальном плане выпуска продукции
- •6.4.2. Задача об оптимальном раскрое материалов (о минимизации отходов)
- •6.4.3. Задача о планировании смен на предприятии
- •6.4.4. Задача о покрытии местности при строительстве объектов
- •6.4.5. Транспортная задача
- •Задача о назначениях (проблема выбора)
- •6.5. Решение задач оптимизации с помощью ms Excel
- •6.5.1. Решение задачи планирования производства
- •Последовательность действий:
- •Контрольные вопросы
- •Литература
- •6.5.2. Решение транспортной задачи
- •Последовательность действий:
- •Глава 1 16
- •Глава 2. 27
- •Глава 3. 51
- •Глава 4. 86
- •Глава 5. 100
- •Глава 6. 125
3.2. Прямые методы решения систем линейных алгебраических уравнений
Прямые методы решения систем линейных алгебраических уравнений основаны на сведении матрицы системы А к матрице простой структуры – диагональной (и тогда решение очевидно) или треугольной – и тогда решение отыскивается с помощью последовательных подстановок. Сведение матрицы А к одному из указанных видов осуществляется при помощи конечного числа элементарных преобразований (см. пункт 3.6.1).
3.2.1. Метод Гаусса
Иногда метод Гаусса называют методом последовательного исключения. Алгоритм исключения неизвестных датируется, по крайней мере, 250-м годом до нашей эры, хотя и носит имя Гаусса.
Суть метода заключается в манипуляциях с уравнениями, в результате чего из уравнений последовательно исключаются неизвестные. Полученная эквивалентная система (т.е. система с тем же самым решением) является системой с треугольной матрицей А.
Процесс решения состоит из двух этапов: прямого и обратного хода.
В результате прямого хода система приводится к системе с треугольной матрицей, а при выполнении обратного хода вычисляются последовательно все неизвестные [8, 13].
Продемонстрируем метод Гаусса на примере системы из трех уравнений. Обозначим каждое уравнение буквами A(i) , B(i), C(i) (здесь (i) соответствует номеру шага).
Прямой ход
Шаг 1.
Допустим ведущий
элемент
отличен от нуля. Разделим первое уравнение
на
.
Полученное при этом уравнение домножим
последовательно на коэффициенты
и
и сложим с соответствующими элементами
2-й и 3-й строки.
Выполняемые действия показаны справа от системы уравнений. В результате выполнения этого шага из всех уравнений, кроме 1-го, исключается неизвестное х1.
Действия:
Шаг 2. Выполняя аналогичные действия со вторым и третьим уравнениями (1-е уравнение при этом остается неизменным), исключаем неизвестное х2 из них:
Действия:
Выполнив два шага для системы 3-го порядка, получили систему, эквивалентную заданной и имеющую верхнюю треугольную матрицу коэффициентов, из которой легко вычисляются все неизвестные. (Для общности можно выполнить 3-й шаг, поделив последнее уравнение на главный коэффициент).
Обратный
ход. Из
последней строки полученной системы
(3.3б)
находим значение неизвестного
Подставляя
его во 2-ую строку системы (3.3б),
получим значение
Имея
,
аналогичным образом найдем
из 1-го уравнения этой же системы:
Рассмотрим простой численный пример.
Пример 3.1. Методом Гаусса решить систему уравнений:
Составим матрицу коэффициентов, включая свободные члены (расширенную матрицу):
Прямой ход
1-й шаг 1-ю строку матрицы делим на а11 =2; Умножаем полученную строку сначала на (–3) и складываем со 2-й, а затем на (–4) и складываем с 3-й:
2-й шаг 2-ю строку матрицы А(1) делим на а22 = –5; Умножаем полученную строку на (–3) и складываем с 3-й строкой этой же матрицы:
Обратный ход
Из последнего уравнения (3-я строка матрицы) получаем
Из
2-го уравнения находим
Из 1-го уравнения получаем
Таким образом, полученное решение имеет вид
Решение этого примера с использованием электронных таблиц Excel приведено в разделе 3.6.1.
В процессе решения системы возможны три случая:
1) Решение системы существует и является единственным, когда матрица коэффициентов невырожденная (при этом на последнем шаге решения получается одно уравнение с одним неизвестным).
2) Система уравнений вообще не имеет решений (такой случай имеет место, когда на некотором шаге получается строка, в которой все коэффициенты при неизвестных равны нулю, а свободный член не равен нулю).
3) Система уравнений имеет бесконечное множество решений (это получается, когда на некотором шаге в системе получается строка, в которой все коэффициенты и свободный член равны нулю).
При практическом применении метода Гаусса следует обратить внимание на следующие моменты:
Если в ходе приведения матрицы А к треугольному виду на главной диагонали окажется элемент, равный нулю, эта схема расчета формально непригодна, хотя система может иметь единственное решение.
В процессе вычислений встречаются ведущие элементы, которые малы по сравнению с другими элементами соответствующих строк. Это обстоятельство может привести к значительным ошибкам округления.
Чтобы избежать всего этого, каждый цикл (шаг) следует начинать с перестановки строк, в результате которой ненулевой элемент перемещается на главную диагональ. При этом среди элементов столбца находится главный элемент, то есть максимальный по модулю в соответствующем столбце, который и выводится на главную диагональ. В таком варианте метода погрешности обычно невелики. Такую модификацию метода называют методом Гаусса с выбором главного элемента.
