Теоретические основы разработки вычислительных систем

Тема 1.1

Численные методы решения инженерных задач

Точность и устойчивость, нелинейные уравнения, СЛАУ, интерполяция и аппроксимация, интегрирование, задача Коши.

Точность вычислений и устойчивость метода

Источники погрешности численного решения:

• неустранимая — погрешность исходных данных и самой математической модели;
• погрешность метода — от замены точной задачи приближённой (например, отбрасывание остатка ряда, конечный шаг сетки h);
• вычислительная (округления) — из-за конечной разрядности представления чисел в ЭВМ.

Меры погрешности. Если x — точное значение, а x̃ — приближённое, то абсолютная погрешность Δ = |x − x̃| (имеет размерность величины), относительная δ = Δ/|x| (безразмерна, обычно в процентах). Относительная погрешность честнее характеризует качество: ошибка 1 см при измерении стола заметна, при измерении стадиона — ничтожна. Верная (значащая) цифра — цифра, абсолютная погрешность которой не превышает половины единицы её разряда: запись x̃ = 2,718 с четырьмя верными цифрами означает Δ ≤ 0,0005.

Катастрофическая потеря точности происходит при вычитании близких чисел: абсолютные погрешности сохраняются, а сам результат мал — относительная погрешность взлетает. Пример: 2,7183 − 2,7180 = 0,0003; если каждое слагаемое известно с точностью 0,0001, относительная ошибка разности достигает 60%. Поэтому формулы стараются преобразовать так, чтобы избежать разности близких величин (например, корни квадратного уравнения при b² ≫ 4ac считают через теорему Виета).

Машинная точность. Числа в ЭВМ хранятся в форме с плавающей точкой (IEEE 754): float — ~7 верных десятичных цифр, double — ~16. Машинный эпсилон ε_м — наименьшее число, для которого 1 + ε_м ≠ 1 в машинной арифметике (~10⁻⁷ для float, ~2·10⁻¹⁶ для double). Отсюда практическое правило: бессмысленно требовать от итераций точность выше машинной, а суммировать длинные ряды лучше от малых членов к большим.

Методы решения нелинейного уравнения f(x) = 0

Этап 1 — отделение корня: находят отрезок [a, b], где f(a)·f(b) < 0 и корень один. Этап 2 — уточнение одним из методов:

• Половинного деления (бисекции) — делим отрезок пополам, оставляем половину со сменой знака. Сходится всегда, но медленно: за шаг интервал сужается вдвое.
• Хорд — новое приближение в точке пересечения хорды, соединяющей (a, f(a)) и (b, f(b)), с осью x.
• Ньютона (касательных): x_k+1 = x_k − f(x_k)/f′(x_k) — пересечение касательной с осью. Квадратичная сходимость вблизи корня, но нужна производная и хорошее начальное приближение.
• Простой итерации — уравнение приводят к виду x = φ(x) и итерируют x_k+1 = φ(x_k).

Как отделяют корни. Три приёма: табличный — вычислить f на сетке и найти смену знака; графический — построить график f (или переписать уравнение в виде g(x) = h(x) и искать пересечения двух простых графиков: например, для x³ = x + 2 — кубической параболы и прямой); аналитический — исследовать f′: между двумя соседними корнями производной лежит не более одного корня функции. Теоретическая основа — теорема Больцано–Коши: непрерывная на [a, b] функция со значениями разных знаков на концах имеет на отрезке хотя бы один корень; если f к тому же строго монотонна — ровно один.

Когда Ньютон гарантированно сходится. Достаточные условия: на [a, b] f(a)·f(b) < 0, а f′ и f″ сохраняют знак (функция монотонна и без перегибов). Начальную точку выбирают из условия f(x₀)·f″(x₀) > 0 — с того конца отрезка, где функция «выпукла в сторону корня»: тогда касательные не выбрасывают за пределы отрезка. Типичные отказы метода: f′(x_k) ≈ 0 — касательная почти горизонтальна и уводит далеко; старт вблизи экстремума — зацикливание; кратный корень (f и f′ обращаются в ноль одновременно) — сходимость падает до линейной.

Модификации Ньютона: упрощённый метод — производная вычисляется один раз в x₀ и замораживается: x_k+1 = x_k − f(x_k)/f′(x₀); сходимость линейная, зато дешёвый шаг; разностный Ньютон — f′ заменяется разностным отношением (при аналитически недоступной производной); для кратных корней — формула x_k+1 = x_k − m·f/f′ с кратностью m восстанавливает квадратичную сходимость.

Сжимающее отображение и сходимость простой итерации

Теорема о сходимости: если φ — сжимающее отображение на отрезке и отображает отрезок в себя, то уравнение x = φ(x) имеет единственную неподвижную точку, и метод простой итерации сходится к ней из любого начального приближения. Практический признак: |φ′(x)| ≤ q < 1 в окрестности корня. Чем меньше q, тем быстрее сходимость; при |φ′| > 1 итерации расходятся. Оценка ошибки: |x_k − x*| ≤ q^k·|x₀ − x*| — геометрическая прогрессия со знаменателем q.

Практические оценки погрешности итераций. Априорная (до счёта): чтобы гарантировать точность ε, достаточно k ≥ ln(|b−a|/ε)/ln(1/q) итераций. Апостериорная (по ходу счёта): |x_k − x*| ≤ q/(1−q)·|x_k − x_k−1| — расстояние до корня оценивается по последнему сдвигу. Отсюда важный нюанс: при q, близком к 1, условие |x_k − x_k−1| < ε ещё не значит, что корень найден с точностью ε — множитель q/(1−q) велик, и останавливаться надо по ужесточённому порогу (1−q)/q·ε.

Прямые и итерационные методы решения СЛАУ

Прямые дают точное (без учёта округлений) решение за конечное число операций:

• Метод Гаусса — прямой ход (приведение к треугольному виду исключением неизвестных) и обратный ход (последовательное вычисление x_n, …, x₁). Трудоёмкость O(n³). Выбор главного элемента снижает влияние округлений.
• LU-разложение — A = LU, решение двух треугольных систем; выгодно при многих правых частях.
• Метод прогонки — вариант Гаусса для трёхдиагональных систем (возникают в разностных схемах), O(n) операций.

Итерационные строят последовательность приближений x^(k) → x*:

• Метод Якоби (простой итерации) — каждая компонента нового приближения считается по всем компонентам старого.
• Метод Гаусса–Зейделя — при вычислении i-й компоненты сразу используются уже уточнённые первые i−1 компонент; обычно сходится быстрее.

Достаточное условие сходимости — диагональное преобладание: |a_ii| > Σ_j≠i |a_ij|. Итерационные методы выгодны для больших разреженных систем.

Почему не Крамер и не обратная матрица. Формулы Крамера x_i = Δ_i/Δ красивы теоретически, но требуют n+1 определителей; их вычисление разложением — O(n!) операций, приведением к треугольному виду — тот же Гаусс, только n+1 раз. Решение через x = A⁻¹b втрое дороже одного Гаусса и менее точно. Практическое правило: обратную матрицу не вычисляют никогда, если нужно лишь решить систему.

Обусловленность СЛАУ. Чувствительность решения к возмущениям данных характеризует число обусловленности cond(A) = ‖A‖·‖A⁻¹‖ ≥ 1: относительная ошибка решения может превышать относительную ошибку правой части в cond(A) раз. Геометрически плохая обусловленность — почти параллельные прямые (гиперплоскости): точка пересечения резко «ездит» при малейшем повороте любой из них. Признаки: малый определитель по сравнению с элементами, огромные элементы A⁻¹, сильное изменение решения при округлении данных.

Системы нелинейных уравнений

• Метод простой итерации: x_k+1 = Φ(x_k); сходится, если норма матрицы Якоби Φ меньше 1 (многомерное сжимающее отображение).
• Метод Ньютона: на каждом шаге решается СЛАУ J(x_k)·Δx = −F(x_k), где J — матрица Якоби; затем x_k+1 = x_k + Δx. Быстрый, но требует вычисления и обращения якобиана на каждом шаге.

При дорогом якобиане применяют модифицированный Ньютон (J вычисляется раз в несколько шагов) и квазиньютоновские методы (якобиан приближается по разностям невязок — метод Бройдена). Сходимость метода Ньютона локальна: вдали от решения его комбинируют с более «живучими» приёмами — дроблением шага или простой итерацией на разгоне.

Интерполяция табличной функции

• Полином Лагранжа: P(x) = Σ y_i·l_i(x), где базисные полиномы l_i(x) = Π_j≠i (x−x_j)/(x_i−x_j) равны 1 в «своём» узле и 0 в остальных. Недостаток: при добавлении узла пересчитывается целиком.
• Полином Ньютона с разделёнными разностями (произвольные узлы): P(x) = f(x₀) + f(x₀,x₁)(x−x₀) + f(x₀,x₁,x₂)(x−x₀)(x−x₁) + …, где разделённые разности строятся рекуррентно. Добавление узла — лишь новое слагаемое.
• Полином Ньютона с конечными разностями (равноотстоящие узлы, шаг h): используются конечные разности Δy_i = y_i+1 − y_i, Δ²y и т.д.; первая формула Ньютона — интерполяция в начале таблицы, вторая — в конце.

Погрешность интерполяции. Если таблица порождена гладкой функцией f, остаточный член

Из формулы видны три рычага точности: гладкость функции (производная f⁽ⁿ⁺¹⁾), число узлов (факториал в знаменателе) и расположение точки x относительно узлов — множитель ω(x) мал внутри таблицы и стремительно растёт вне её. Отсюда правило: экстраполяция (выход за пределы таблицы) на порядок опаснее интерполяции. Рост ω у краёв отрезка при равноотстоящих узлах — причина эффекта Рунге; лекарство — узлы Чебышёва, сгущающиеся к краям (проекции равномерно расставленных точек полуокружности): они минимизируют max|ω(x)| и убирают раскачку.

Обратная интерполяция — найти x, при котором функция принимает заданное значение y*: достаточно поменять ролями столбцы таблицы (строить полином x = P(y)), если функция монотонна. Классическое применение — уточнение корня по таблице значений f.

Сплайн-интерполяция. Вместо одного полинома высокой степени промежуток разбивают на части и на каждой строят полином малой степени, сшивая куски гладко. Кубический сплайн — на каждом отрезке полином 3-й степени; в узлах непрерывны сама функция, первая и вторая производные. Это стандартный ответ на эффект Рунге: гладкая кривая без раскачки краёв. Именно так работают лекала чертёжника и кривые в CAD.

Аппроксимация. Метод наименьших квадратов

МНК: параметры функции φ(x, a₀…a_m) выбирают из минимума суммы квадратов отклонений

Условия минимума ∂S/∂a_k = 0 дают систему нормальных уравнений — линейную СЛАУ относительно коэффициентов. Для прямой φ = a + bx получается система 2×2:

Нелинейные модели сводят к линейным заменой переменных. Показательную зависимость y = a·e^bx логарифмируют: ln y = ln a + bx — прямая в координатах (x, ln y); степенную y = a·x^b — прямая в координатах (ln x, ln y); гиперболу y = a + b/x линеаризует замена u = 1/x. Дальше работает обычный МНК для прямой. Это стандартный экзаменационный приём: «как подобрать экспоненту по данным» = «прологарифмируй и подгони прямую».

Выбор степени аппроксимирующего полинома. Степень увеличивают, пока сумма квадратов отклонений S заметно падает; как только падение прекращается — остановиться: дальнейший рост степени ловит шум, а не закономерность (переобучение). Ориентир: остаточная дисперсия S/(n − m − 1) (n точек, m+1 коэффициентов) должна сравняться с дисперсией ошибки измерений. Число точек должно заметно превышать число коэффициентов — иначе аппроксимация вырождается в интерполяцию со всеми её осцилляциями.

Численное интегрирование и дифференцирование

Интеграл заменяют квадратурной суммой по значениям функции в узлах на сетке с шагом h:

• Прямоугольников (левых/правых/средних) — точность O(h) для левых/правых, O(h²) для средних;
• Трапеций — площадь трапеций между узлами, точность O(h²);
• Симпсона (парабол) — участок из пары шагов заменяется параболой, точность O(h⁴), число шагов чётное.

Практическая оценка точности — правило Рунге: считают с шагами h и h/2 и сравнивают результаты.

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

Остаточные члены составных формул (M — максимум соответствующей производной на отрезке):

Любопытно: средние прямоугольники вдвое точнее трапеций (константа 24 против 12) — касательная в середине шага «обманывает» кривизну лучше хорды. По остаточному члену решают и обратную задачу — выбор шага под заданную точность: из (b−a)·M₂·h²/12 ≤ ε получаем h ≤ √(12ε/((b−a)M₂)).

Другие квадратурные формулы (семейство Ньютона–Котеса и не только):

• Правило 3/8 — кубическая парабола по трём шагам: (3h/8)·(f₀ + 3f₁ + 3f₂ + f₃); тот же порядок O(h⁴), что у Симпсона, применяется, когда число шагов кратно трём.
• Квадратуры Гаусса — узлы не равноотстоящие, а выбираются оптимально (корни полиномов Лежандра): n узлов дают точность для полиномов степени 2n−1 — вдвое «умнее» Ньютона–Котеса.

Метод Монте-Карло

Метод статистических испытаний (Монте-Карло) — вычисление интеграла случайными точками: бросаем N точек равномерно в прямоугольник, накрывающий график; доля точек, попавших под кривую, умноженная на площадь прямоугольника, оценивает интеграл. Точность растёт как 1/√N — медленно (для лишнего знака нужно в 100 раз больше точек), зато скорость не зависит от размерности: для 100-мерного интеграла (частая ситуация в статистике и машинном обучении) сеточные методы бессильны, а Монте-Карло работает так же.

Дифференцирование — заменой производной разностными отношениями: правая/левая разность (y_i+1−y_i)/h — O(h), центральная (y_i+1−y_i−1)/2h — O(h²), вторая производная (y_i+1−2y_i+y_i−1)/h² — O(h²). Операция некорректна к шуму: при уменьшении h ошибки данных усиливаются.

Оптимальный шаг дифференцирования. Полная ошибка складывается из погрешности аппроксимации (~h²) и вычислительной (~ε/h, где ε — ошибка значений функции): при слишком малом h вторая доминирует. Минимум суммы даёт h_опт ~ ∛ε для центральной разности — шаг нельзя уменьшать бесконечно, у численного дифференцирования есть «дно» точности. В этом смысле задача некорректна, и на практике производные экспериментальных данных получают дифференцированием сглаживающего полинома МНК или сплайна.

Задача Коши. Методы Эйлера и Рунге–Кутта

• Метод Эйлера: y_i+1 = y_i + h·f(x_i, y_i) — движение по касательной. Первый порядок точности O(h), ошибка быстро накапливается.
• Модифицированный Эйлер (Эйлера–Коши) — с пересчётом по среднему наклону, O(h²).
• Рунге–Кутта 4-го порядка: наклон усредняется по четырём пробным вычислениям f внутри шага. Точность O(h⁴) — стандарт де-факто:

Классификация методов для ОДУ, которую полезно назвать:

• одношаговые (Эйлер, Рунге–Кутта) — шаг только из текущей точки; легко стартуют и меняют шаг;
• многошаговые (Адамса) — используют несколько предыдущих точек: та же точность при меньшем числе вычислений f, но нужен «разгон» одношаговым методом;
• явные / неявные — в неявных y_i+1 входит в обе части и находится решением уравнения; они устойчивее и незаменимы для жёстких систем, где явные методы требуют неприемлемо малого шага.

Уравнения высших порядков и системы. Методы Эйлера и Рунге–Кутта формулируются для y′ = f(x, y), но y можно понимать как вектор — те же формулы покомпонентно решают системы ОДУ. Уравнение n-го порядка сводится к системе n уравнений первого порядка заменой z₁ = y, z₂ = y′, …: например, колебание y″ + 2y′ + 5y = 0 превращается в z₁′ = z₂, z₂′ = −5z₁ − 2z₂. Поэтому «решатель задачи Коши» один на все случаи — от остывания чашки до динамики манипулятора.

Локальная и глобальная ошибка. Локальная — промах одного шага при точном старте: у Эйлера O(h²), у РК4 — O(h⁵). Глобальная — накопленный промах на всём отрезке: на порядок ниже локальной (шагов ~1/h), отсюда O(h) и O(h⁴). Автоматический выбор шага в практических решателях: на каждом шаге ошибка оценивается правилом Рунге (шаг h против двух шагов h/2) или вложенной парой методов разных порядков (Рунге–Кутта–Фельберг); если оценка больше допуска — шаг уменьшают и повторяют, если сильно меньше — увеличивают. Так решатель сам семенит на крутых участках решения и шагает широко на пологих.

Тема 1.2

Математическое моделирование

Модели и их свойства, аналогии подсистем, способы формирования моделей, краевые задачи: МКР и МКЭ.

Основные понятия

Назначение моделей: анализ и прогноз поведения объекта, проектирование и оптимизация, управление, обучение.

Этапы математического моделирования (схема «модель — алгоритм — программа» по А. А. Самарскому):

1. Содержательная постановка — что известно об объекте, на какие вопросы должна ответить модель, с какой точностью.
2. Построение ММ — выбор существенных свойств, запись уравнений и условий; здесь же принимаются упрощающие допущения (и фиксируются: они определят область адекватности).
3. Выбор или разработка численного метода — дискретизация, оценка устойчивости и трудоёмкости (материал темы 1.1).
4. Программная реализация и её верификация — проверка, что программа решает именно записанные уравнения (тесты на задачах с известным решением).
5. Проверка адекватности — сравнение расчётов с экспериментом на контрольных данных, не использованных при настройке модели.
6. Вычислительный эксперимент — многократные расчёты вместо натурных опытов; по результатам модель уточняется, и цикл повторяется.

Классификация ММ

Дополнительные разрезы классификации, которые полезно назвать: по параметрам — с сосредоточенными (ОДУ: вся деталь описана одной температурой) и с распределёнными параметрами (УрЧП: температура — поле по координатам); по форме представления — аналитические (явные формулы), алгоритмические (вычислительная процедура) и имитационные (воспроизведение поведения системы во времени по шагам, включая случайные события — очереди, отказы; исследуются статистикой многих прогонов). Непрерывные и дискретные модели различаются характером переменных: течение в трубе — непрерывная модель, работа склада поштучных изделий — дискретная (дискретно-событийная имитация).

Свойства моделей и способы получения

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

Способы получения моделей:

• аналитический (теоретический) — из фундаментальных законов (сохранения массы, энергии, импульса, законов Кирхгофа, Ньютона): широкая область адекватности, но требует знания физики процессов;
• экспериментальный (формальный) — обработкой опытных данных (регрессия, МНК, планирование эксперимента): модель «чёрного ящика», работает только в области эксперимента;
• экспериментально-аналитический — структура из теории, коэффициенты из эксперимента (модель «серого ящика»).

Аналогии между подсистемами. Топологические и компонентные уравнения

Однородные физические подсистемы описываются одинаковыми по форме уравнениями через пары переменных: фазовую переменную типа потока и типа потенциала.

К поступательной механике добавляется вращательная: поток — момент M, потенциал — угловая скорость ω, аналог C — момент инерции, аналог R — вращательное трение, аналог L — крутильная податливость вала. Полный набор элементов эквивалентной схемы — три пассивных типа плюс два вида источников: источник потенциала (ЭДС, насос заданного давления, печь заданной температуры) и источник потока (источник тока, насос заданного расхода, нагреватель заданной мощности).

Три типа пассивных элементов различаются тем, что они делают с энергией: R-тип рассеивает (трение, электрическое и термическое сопротивление), C-тип накапливает энергию через переменную типа потенциала (конденсатор, масса, теплоёмкость), L-тип — через переменную типа потока (индуктивность, упругость). Их компонентные уравнения имеют одинаковую форму во всех подсистемах:

У тепловой и массообменной подсистем аналога L нет — в природе не наблюдается «тепловая индуктивность» (тепловой поток не обладает инерцией). Это стоит упомянуть как границу применимости аналогий.

• Компонентные уравнения описывают отдельные элементы (связь тока и напряжения резистора, силы и скорости демпфера).
• Топологические уравнения описывают соединение элементов и следуют из структуры системы — аналоги законов Кирхгофа: сумма потоков в узле равна нулю, сумма потенциалов по контуру равна нулю.

Благодаря аналогиям любую однородную подсистему можно представить эквивалентной схемой из R-, C-, L-элементов и источников, а моделировать единым программным аппаратом.

Способы формирования ММ систем: обобщённый метод — в систему включаются все компонентные и топологические уравнения (переменные — все токи и напряжения ветвей); узловой метод — неизвестные только узловые потенциалы, уравнения — балансы потоков в узлах (размерность меньше, применяется в СAПР схемотехники).

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

Краевая задача — уравнение (обычно в частных производных) плюс условия на границах области (и начальные условия для нестационарных задач).

Типы уравнений математической физики и их «физика»: эллиптические (уравнение Лапласа/Пуассона) — стационарные поля: установившаяся температура, электростатика; параболические (теплопроводности/диффузии) — необратимые процессы выравнивания во времени; гиперболические (волновое) — колебания и распространение волн с конечной скоростью. Тип диктует и постановку условий, и выбор метода: для эллиптических — только граничные условия, для параболических и гиперболических — ещё и начальные.

Типы граничных условий: I рода (Дирихле) — задано значение функции на границе (температура стенки); II рода (Неймана) — задана производная (тепловой поток; частный случай — теплоизоляция, поток нулевой); III рода — линейная связь функции и производной (теплообмен со средой по закону Ньютона: −λ∂T/∂n = α(T − T_ср)). На разных участках границы могут стоять условия разных родов — смешанная задача.

Метод конечных разностей (МКР)

• Область покрывается сеткой; производные заменяются разностными отношениями; УрЧП превращается в систему алгебраических уравнений относительно значений в узлах.
• Погрешность аппроксимации — невязка от замены производных разностями, оценивается разложением в ряд Тейлора: O(h), O(h²)…
• Явная схема: значение на новом временном слое выражается непосредственно через известные значения старого слоя. Проста, но условно устойчива — шаг по времени ограничен (например, для уравнения теплопроводности Δt ≤ h²/2a).
• Неявная схема: в уравнение входят несколько неизвестных нового слоя — на каждом шаге решается СЛАУ (для одномерной задачи — прогонкой). Безусловно устойчива, шаг ограничен только точностью.
• Устойчивость разностной схемы — ошибки, внесённые на одном слое, не нарастают при переходе к следующим. Сходимость = аппроксимация + устойчивость.

Сходимость = аппроксимация + устойчивость — это теорема эквивалентности Лакса, главный теоретический факт о разностных схемах: если схема аппроксимирует корректную задачу и устойчива, то при измельчении сетки её решение сходится к точному, причём порядок сходимости равен порядку аппроксимации. Аппроксимация без устойчивости бесполезна: ошибки округления взорвут счёт раньше, чем скажется точность формул.

Промежуточный вариант — схема Кранка–Николсона: пространственная производная берётся полусуммой значений старого и нового слоёв. Схема неявная (нужна прогонка), безусловно устойчивая и при этом второго порядка по времени O(Δt²) — против первого у чисто явной и чисто неявной; стандарт для уравнения теплопроводности.

Устойчивость для уравнений переноса и волн. Для гиперболических уравнений явные схемы устойчивы при условии Куранта (CFL): a·Δt/h ≤ 1 — за один шаг по времени возмущение не должно «перепрыгивать» ячейку сетки; число s = a·Δt/h называют числом Куранта. Смысл тот же, что у Δt ≤ h²/2a для теплопроводности: шаг по времени подчинён шагу по пространству, только для волн ограничение линейное (Δt ~ h), а для диффузии — квадратичное (Δt ~ h²), поэтому явные схемы для диффузии особенно невыгодны на мелких сетках.

Метод конечных элементов (МКЭ)

• Область разбивается на конечные элементы произвольной формы (треугольники, тетраэдры); решение внутри элемента приближается простыми базисными функциями (обычно полиномами).
• Коэффициенты находятся из минимизации функционала (вариационная постановка) или метода взвешенных невязок (Галёркина); собирается глобальная СЛАУ с разреженной матрицей.
• Преимущества перед МКР: естественно описывает сложную геометрию и граничные условия, легко сгущает сетку локально.

Алгоритм МКЭ по шагам (как его рассказывают на «отлично»):

1. Дискретизация — область разбивается на элементы (2D: треугольники, четырёхугольники; 3D: тетраэдры, гексаэдры), выделяются узлы.
2. Выбор базисных функций — на каждом элементе решение приближается полиномом через узловые значения; базисная функция узла равна 1 в «своём» узле, нулю в остальных и отлична от нуля лишь на соседних элементах (локальный носитель — причина разреженности матрицы).
3. Локальные матрицы — для каждого элемента из вариационной постановки или метода Галёркина вычисляется матрица «жёсткости» и вектор нагрузки.
4. Ансамблирование — локальные матрицы складываются в глобальную СЛАУ K·u = F по соответствию местных и глобальных номеров узлов.
5. Учёт граничных условий — условия Дирихле фиксируют узловые значения, Неймана входят в вектор нагрузки.
6. Решение СЛАУ (разреженные прямые или итерационные методы) и постобработка — восстановление полей, градиентов, напряжений.

Идея Галёркина, на которой держится шаг 3: потребовать, чтобы невязка приближённого решения была ортогональна всем базисным функциям — «ошибка не должна быть видна ни одному из кирпичиков, из которых строим решение». Для задач механики эквивалентная формулировка — минимум потенциальной энергии, поэтому матрицу K и называют матрицей жёсткости.

Метод прямых (сведение к ОДУ) и метод характеристик

Метод прямых: производные лишь по части переменных заменяются разностями — УрЧП сводится к системе ОДУ, которую решают методами типа Рунге–Кутта.

Метод характеристик — специальный метод для гиперболических УрЧП (волновое уравнение, перенос вещества потоком, нестационарные течения газа). У таких уравнений есть характеристики — выделенные кривые в плоскости (x, t), вдоль которых возмущения распространяются с конечной скоростью, а само УрЧП вырождается в обыкновенное дифференциальное уравнение (соотношение совместности). Алгоритм: из точек с известными данными выпускаются характеристики; в точке их пересечения интегрированием ОДУ вдоль каждой кривой находится решение — сетка строится «сама», следуя физике переноса.

Сравнение: МКР универсален для всех типов уравнений (параболических, эллиптических, гиперболических), метод характеристик точнее отслеживает фронты и разрывы, но применим только к гиперболическим задачам и сложен в многомерье.

Тема 1.3

Оптимизация

Постановка задач, одномерные и многомерные методы, нелинейное программирование, вариационное исчисление.

Постановка задачи и классификация

Общая задача математического программирования: f₀(X) → min при ограничениях-неравенствах f_i(X) ≥ 0, i = 1…p, и ограничениях-равенствах f_i(X) = 0, i = p+1…m. Если X^d совпадает со всем пространством — задача безусловной оптимизации, иначе — условной.

Критерий оптимального проектирования и его связь с математической моделью (формулировка билета): критерий — количественная оценка качества проектного решения (себестоимость, энергозатраты, точность), а вычисляется он через выходные координаты объекта, которые связаны с варьируемыми переменными (конструктивными и режимными параметрами) уравнениями математической модели. Уравнения ММ выступают уравнениями связи задачи оптимизации: оптимизатор предлагает значения варьируемых переменных → модель рассчитывает по ним выходные координаты → по ним вычисляется критерий; ограничения (физическая реализуемость, технологические пределы) замыкают допустимую область.

Критерии оптимальности при нескольких показателях качества:

• частный — один главный показатель, остальные переводятся в ограничения;
• аддитивный — взвешенная сумма частных критериев F = Σ w_if_i;
• мультипликативный — произведение F = Π f_i^w_i;
• максиминный — максимизация худшего из частных критериев: max min_i f_i (гарантированный результат).

Ограничения: равенства g(x) = 0, неравенства h(x) ≤ 0, прямые (a ≤ x_i ≤ b). Классификация задач: безусловная / условная; одномерная / многомерная; линейное программирование (критерий и ограничения линейны), нелинейное (хотя бы одна функция нелинейна), дискретное (допустимое множество конечно или счётно) и его частный случай целочисленное (все допустимые точки целочисленны); задачи оптимального управления (искомая величина — функция времени).

Характеристика численных методов: методы спуска строят последовательность точек с убыванием критерия; конечношаговые методы достигают решения за конечное число шагов (симплекс-метод ЛП), бесконечношаговые — лишь в пределе. Порядок метода — старший порядок используемых производных (нулевой, первый, второй). Критерии окончания: |x_k+1 − x_k| < ε, |F_k+1 − F_k| < ε, ‖∇F‖ < ε.

Линейное и целочисленное программирование

Задача линейного программирования (ЛП): критерий и все ограничения — линейные функции переменных:

Классика применения: планирование производства (максимум прибыли при ограниченных ресурсах), транспортная задача (минимум стоимости перевозок), смеси (дешёвейшая рецептура заданных свойств). Геометрия ЛП: допустимая область — выпуклый многогранник (пересечение полуплоскостей), линии уровня критерия — параллельные гиперплоскости, поэтому оптимум всегда достигается в вершине многогранника (или на целой грани — тогда решений бесконечно много).

Симплекс-метод — направленный перебор вершин: старт в любой допустимой вершине; переход к соседней вершине, где критерий лучше; остановка, когда все соседи хуже — для выпуклой задачи это глобальный оптимум. Число вершин конечно, значит метод конечношаговый. Алгебраически вершина — базисное допустимое решение (часть переменных нулевые), переход — замена одной базисной переменной по правилам симплекс-таблицы.

Целочисленное программирование — те же задачи, но переменные обязаны быть целыми (станки, люди, рейсы — «полстанка» не бывает). Округление непрерывного оптимума в общем случае неверно: округлённая точка может нарушить ограничения или оказаться далеко от целочисленного оптимума. Точные методы:

• метод ветвей и границ — решается ЛП без требования целочисленности (релаксация); по дробной переменной x = 2,6 задача ветвится на две подзадачи (x ≤ 2 и x ≥ 3); оценки-границы из релаксаций позволяют отсекать бесперспективные ветви целиком;
• метод отсечений Гомори — к релаксации добавляются дополнительные линейные ограничения (отсечения), отрезающие дробный оптимум, но не задевающие ни одной целой точки; повторяется до целочисленного решения.

Одномерная оптимизация

Условия оптимальности: необходимое — F′(x*) = 0; достаточное — F″(x*) > 0 (минимум). Численные методы сужают интервал неопределённости, где лежит минимум унимодальной функции:

• половинного деления — пробные точки на четвертях отрезка: x₁ = a + 0,25(b − a) и x₂ = b − 0,25(b − a) (делят пополам левую и правую половины); если F(x₁) < F(x₂) — исключается [x₂, b], если F(x₁) > F(x₂) — исключается [a, x₁]: интервал сокращается на 25% за итерацию ценой двух вычислений (по методичке Литовки);
• «золотого» сечения — пробные точки делят интервал в отношении золотого сечения (τ ≈ 0,618), одна из точек переиспользуется на следующем шаге: одно вычисление функции за итерацию, сжатие в 0,618 раза;
• Фибоначчи — точки по числам Фибоначчи; при заданном числе вычислений даёт минимальный интервал (оптимальный пассивно-последовательный план).

Метод Ньютона для оптимизации — это метод касательных, применённый к уравнению F′(x) = 0:

Сходится за считанные шаги вблизи минимума, но требует двух производных и хорошего старта: при F″ < 0 шагнёт к максимуму. Методы интервалов (половинное деление, золотое сечение, Фибоначчи) медленнее, зато не требуют производных и гарантированно работают на любой унимодальной функции.

Многомерная оптимизация

Условия: необходимое — ∇F(x*) = 0; достаточное — матрица Гессе положительно определена (минимум).

• Методы нулевого порядка (только значения F): покоординатный спуск (Гаусса–Зейделя) — поочерёдная одномерная минимизация по каждой координате; метод Пауэлла — покоординатный спуск с построением сопряжённых направлений; симплексный метод (Нелдера–Мида) — деформируемый многогранник: отражение, растяжение, сжатие худшей вершины.
• Методы первого порядка: градиентный — шаг против градиента x_k+1 = x_k − λ∇F; наискорейшего спуска — λ на каждом шаге из одномерной минимизации вдоль антиградиента (траектория из взаимно перпендикулярных шагов); сопряжённых градиентов — направления корректируются с учётом предыдущих, квадратичную функцию n переменных минимизирует за n шагов.
• Метод «оврагов» — для функций с вытянутыми «оврагами», где градиентные методы «пилят» поперёк оврага: из двух близких точек спускаются на дно, затем делают большой шаг вдоль дна оврага.

Покоординатный спуск подробнее: фиксируем все переменные, кроме x₁, и решаем одномерную задачу (золотым сечением); затем по x₂, и так по кругу, пока смещение за полный цикл не станет меньше ε. Работает хорошо, когда переменные слабо связаны (линии уровня вытянуты вдоль осей), и вязнет, когда овраг повёрнут к осям под 45° — каждая координата «мешает» другой.

Метод Пауэлла лечит именно это: после цикла покоординатных спусков направление «суммарного сдвига» за цикл (от начальной точки цикла к конечной) добавляется в набор направлений вместо одного из старых — постепенно набор превращается в систему сопряжённых направлений, вдоль которых квадратичная функция минимизируется без взаимных помех (за n циклов). Это лучший метод нулевого порядка для гладких функций.

Симплекс Нелдера–Мида по шагам: n+1 вершина (треугольник при n = 2), упорядочиваются по значению F; худшая вершина отражается через центр тяжести остальных (коэффициент α = 1); если новая точка лучшая — растяжение (γ = 2); если хуже всех остальных — сжатие (β = 0,5); если и это не помогло — редукция: все вершины стягиваются к лучшей вдвое. Критерий останова — «сплющивание» симплекса: разброс значений F по вершинам меньше ε.

Метод «оврагов» по шагам: из двух близких стартов независимо делают несколько градиентных шагов — обе точки скатываются на дно оврага; прямая через них приближает направление дна; вдоль неё делается большой «овражный» шаг; из новой точки процедура повторяется. Метод не даёт точного минимума, но быстро проводит вдоль оврага туда, где обычный градиентный спуск дожмёт.

Методы случайного поиска (нулевой порядок; в билетах встречаются прямо по названиям вариантов):

• с постоянным радиусом поиска и случайным направлением: из текущей точки X^k делается пробный шаг X = X^k + h·ξ, где ξ — случайный вектор единичной длины (случайное направление), h — радиус поиска. Если F(X) < F(X^k) — шаг удачный, переходим в X; иначе бросаем новое случайное направление. Если много проб подряд неудачны — минимум близко, радиус h уменьшают;
• с обратным шагом: при неудачной пробе (функция выросла) следующий шаг делается в противоположном направлении −ξ — раз «в гору», значит обратно, скорее всего, «под гору»: неудачная проба тоже приносит информацию;
• достоинства: предельная простота (нужны только значения F), нечувствительность к разрывам и «шуму» функции, способность выскакивать из локальных минимумов; недостаток — медленная сходимость, поэтому случайный поиск часто используют для грубого поиска с последующим уточнением детерминированным методом.

Методы второго порядка. Метод Ньютона: шаг x_k+1 = x_k − H⁻¹∇F использует матрицу Гессе H (вторые производные) — учитывает кривизну и на квадратичной функции попадает в минимум за один шаг из любой точки. Дорог: n² вторых производных и обращение матрицы на каждом шаге. Квазиньютоновские методы (ДФП — Дэвидона–Флетчера–Пауэлла, БФГШ) — компромисс: приближение H⁻¹ накапливается по разностям градиентов соседних шагов, вторые производные не вычисляются вовсе.

Нелинейное программирование

Ограничения-равенства — метод множителей Лагранжа: строится функция L(x, λ) = F(x) + Σ λ_jg_j(x); необходимые условия — равенство нулю всех частных производных L по x и по λ. Множитель λ_j показывает чувствительность оптимума к ослаблению j-го ограничения.

Ограничения-неравенства — условия Куна–Таккера; решение соответствует седловой точке функции Лагранжа: по x — минимум, по λ ≥ 0 — максимум.

Полный набор условий Куна–Таккера для задачи min F при g_i(x) ≤ 0, h_j(x) = 0 (стоит уметь перечислить все четыре группы):

• стационарность: ∇F + Σλ_i∇g_i + Σμ_j∇h_j = 0 — антиградиент критерия «уравновешен» градиентами активных ограничений;
• допустимость: g_i(x*) ≤ 0, h_j(x*) = 0;
• неотрицательность множителей неравенств: λ_i ≥ 0 (знаки μ_j произвольны);
• дополняющая нежёсткость: λ_i·g_i(x*) = 0 — каждое ограничение либо активно, либо имеет нулевую цену.

Для выпуклых задач (выпуклый критерий, выпуклая допустимая область) эти условия не только необходимы, но и достаточны, а любой локальный минимум — глобальный. Практический смысл: решение задачи НЛП сводится к перебору гипотез о составе активных ограничений — как в примере выше, где проверялись случаи λ = 0 и g = 0.

Численные методы НЛП:

• прямые — работают в допустимой области: прямой поиск с возвратом (нарушили ограничение — вернулись и уменьшили шаг), метод проекции градиента (шаг проецируется на границу допустимой области);
• Прямой поиск с возвратом подробнее: движение любым безусловным методом (например, градиентным); как только очередная точка нарушила ограничение — возврат в последнюю допустимую точку и повтор шага с уменьшенным (обычно вдвое) размером; вблизи границы траектория «ощупью» скользит вдоль неё. Проекция градиента подробнее: если точка на границе, антиградиент раскладывается на нормальную (к границе) и касательную составляющие; шаг делается вдоль касательной — проекции антиградиента на границу; для линейного ограничения aᵀx = b проекция вычисляется явно: p = −(I − aaᵀ/aᵀa)∇F. Останов — когда проекция антиградиента нулевая, то есть выполнены условия Куна–Таккера;
• методы штрафных функций — сводят условную задачу к последовательности безусловных. По методичке Литовки: для задачи f₀(X) → min при f_i(X) ≥ 0 строится функция R(X, K) = f₀(X) + S(K, f_i(X)), где K — коэффициент штрафа, S — функция штрафа за нарушение ограничений; решается последовательность безусловных задач min R(X, K_i), и при K_i → ∞ их минимумы стремятся к решению исходной задачи. Метод внешней точки: штраф включается при выходе из допустимой области, например S = K·Σ(min(0, f_i(X)))² — приближение к решению снаружи. Метод внутренней точки (барьерный): штраф резко растёт при подходе к границе изнутри, например S = −(1/K)·Σ ln f_i(X) или S = (1/K)·Σ 1/f_i(X) — все точки остаются допустимыми, но стартовать нужно строго внутри области. Комбинированный метод — внутренний штраф для неравенств и внешний для равенств одновременно.

Вариационное исчисление

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

Простейшая задача: минимизировать J[y] при закреплённых концах y(a), y(b). Необходимое условие экстремума — уравнение Эйлера:

Для функционалов со старшими производными F(x, y, y′, y″, …) — уравнение Эйлера–Пуассона: F_y − d/dx F_y′ + d²/dx² F_y″ − … = 0. Частные случаи интегрируемости: если F не зависит от y, то F_y′ = C; если F не зависит от x — первый интеграл F − y′F_y′ = C.

Связь с оптимальным управлением. Задача оптимального управления — развитие вариационного исчисления: ищется управление u(t), минимизирующее функционал при связях-уравнениях движения объекта ẋ = f(x, u) и ограничениях на управление (u ∈ U — например, |u| ≤ u_max, чего классическое вариационное исчисление не умеет). Необходимые условия даёт принцип максимума Понтрягина — обобщение уравнений Эйлера; типичный результат — релейное управление («банг-банг»): оптимальное u скачет между крайними значениями, как в задаче о быстрейшем разгоне-торможении.

Численные методы: уравнение Эйлера — краевая задача для ОДУ, решается методом пристрелки (подбор недостающего начального условия так, чтобы попасть в правое краевое) или прогонкой (для линейных задач). Прямые методы минимизируют сам функционал: метод Ритца — решение ищется как комбинация базисных функций y ≈ Σ a_iφ_i(x), задача сводится к минимизации функции коэффициентов; метод Канторовича — обобщение для функционалов от функций многих переменных (коэффициенты — функции); конечно-разностный метод Эйлера — интеграл заменяется суммой по сетке, функционал становится функцией узловых значений.

Условный экстремум: связи бывают голономные (φ(x, y₁, y₂, …) = 0 — без производных), неголономные (дифференциальные, с y′), изопериметрические (∫G dx = const — заданная «длина»). Необходимые условия строятся методом множителей Лагранжа: вспомогательный функционал с λ(x) (для изопериметрических λ — константа), для него записывается уравнение Эйлера.

Тема 1.4

Искусственный интеллект

Экспертные системы, представление знаний, нечёткие знания, модели поиска решений — по методичкам Коробовой и Обухова.

Подходы к искусственному интеллекту

Причина появления ИИ — потребность решать неформализованные задачи: без строгого алгоритма, с неполными и нечёткими данными, где решение строится на знаниях экспертов. Два исторических подхода:

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

Признаки неформализованных задач (по Э. Фейгенбауму): алгоритмическое решение неизвестно или невыполнимо по ресурсам; данные ошибочны, неоднозначны, неполны; цели нельзя выразить точной целевой функцией; задача решается на символьном уровне (понятия, а не числа). Классические области: медицинская и техническая диагностика, интерпретация данных, планирование, проектирование, обучение.

Немного истории для ответа «своими словами»: 1950 — критерий Тьюринга (машина «интеллектуальна», если в диалоге неотличима от человека); 1956 — Дартмутский семинар, рождение термина «artificial intelligence»; 1960–70-е — расцвет символьного подхода и первые ЭС (DENDRAL — определение структуры молекул, MYCIN — диагностика инфекций); 1980-е — промышленный бум ЭС и языков Prolog/Lisp; с 2010-х доминирует восходящий подход — глубокие нейронные сети. Современная тенденция — гибрид: нейросети извлекают закономерности из данных, символьные методы дают объяснимость и логику.

Экспертные системы

• База знаний — формализованные знания предметной области: факты и правила.
• Механизм логического вывода — применяет правила к фактам, строит цепочку рассуждений.
• Модуль извлечения (приобретения) знаний — пополнение БЗ инженером знаний в диалоге с экспертом.
• Система объяснений — отвечает «почему получен такой вывод» перечнем сработавших правил (доверие пользователя, отладка БЗ).

Методология разработки ЭС (этапы): идентификация задачи → концептуализация (выделение понятий и связей) → формализация (выбор модели представления знаний) → выполнение (наполнение БЗ) → тестирование → опытная эксплуатация. Разработка ведётся быстрым прототипом с постепенным расширением: демонстрационный → исследовательский → действующий → промышленный → коммерческий уровень. Трудности: извлечение знаний у эксперта («узкое горло» инженерии знаний), верификация полноты и непротиворечивости БЗ, сопровождение. Перспективы: гибридные системы (правила + нейросети + нечёткая логика), самообучающиеся системы, интеграция с большими данными.

Участники разработки: эксперт — носитель знаний предметной области, источник правил; инженер по знаниям (когнитолог) — посредник, извлекающий знания у эксперта и формализующий их в выбранной модели; программист — реализует или настраивает инструментальные средства; пользователь — специалист, для которого система становится «советчиком». Именно связка «эксперт — инженер знаний» определяет качество ЭС, а не программный код.

Классификация ЭС: по типу решаемой задачи — интерпретация данных, диагностика, мониторинг, прогнозирование, планирование, проектирование, обучение, управление; по связи с реальным временем — статические (данные не меняются за сеанс: диагностика по анализам) и динамические (данные поступают в темпе процесса: мониторинг реактора, требуется пересмотр выводов на лету); по степени интеграции — автономные и гибридные (модуль в составе САПР или АСУ).

Инструментальные средства построения ЭС (способы построения): программирование «с нуля» на языках ИИ (Prolog — логический вывод «из коробки», Lisp — обработка символьных структур); оболочки ЭС — готовый механизм вывода и интерфейс, наполняется только база знаний (классика — EMYCIN, современные — CLIPS, Drools); гибридные инструментальные среды с несколькими моделями представления знаний. Выбор — компромисс: оболочка ускоряет разработку на порядок, но привязывает к своей модели знаний.

Способы представления знаний

• Продукционные правила — «ЕСЛИ условие ТО действие». Наглядны, модульны, легко пополняются; основной способ в ЭС.
• Фреймы — структура-«анкета» для стереотипной ситуации: имя, слоты со значениями, значениями по умолчанию, присоединёнными процедурами; фреймы образуют иерархии с наследованием.
• Семантические сети — ориентированный граф: вершины — понятия, дуги — отношения (is-a «является», part-of «часть», свойства). Вывод — поиск по сети.
• Логические модели — исчисление предикатов, вывод по правилам формальной логики (резолюция).
• Нейронные сети — знания в виде весов связей искусственных нейронов; нейрон вычисляет взвешенную сумму входов и пропускает через функцию активации; сети обучаются на примерах (обратное распространение ошибки), но не объясняют вывод.

Декларативные и процедурные знания. Декларативные — «что истинно» (факты, описания, отношения: семантические сети, фреймы); процедурные — «как действовать» (правила, процедуры). Продукционная модель объединяет оба вида: посылка декларативна, действие процедурно. Ещё один разрез — поверхностные знания (эмпирические ассоциации «симптом → диагноз») и глубинные (понимание механизма: анатомия, физика отказа); промышленные ЭС первого поколения строились на поверхностных, современные стремятся к глубинным — они устойчивее на нетиповых случаях.

Как работает продукционный цикл вывода: 1) сопоставление — находятся все правила, посылки которых удовлетворены содержимым рабочей памяти (они образуют конфликтное множество); 2) разрешение конфликта — выбор одного правила: по приоритету, по специфичности (правило с более подробной посылкой предпочтительнее), по свежести данных, по порядку в БЗ; 3) выполнение — действие правила меняет рабочую память; цикл повторяется до цели или пустого конфликтного множества.

Неопределённость в правилах. Знания экспертов редко категоричны, поэтому правилам приписывают коэффициенты уверенности (CF ∈ [−1; 1], подход MYCIN): уверенность заключения = уверенность посылки × CF правила; при нескольких условиях в посылке берётся min их уверенностей; независимые свидетельства в пользу одного вывода комбинируются по формуле CF = CF₁ + CF₂·(1 − CF₁), усиливая друг друга, но не превышая 1. Альтернативные аппараты — байесовские сети (строгая вероятность) и нечёткая логика (следующий подраздел).

Нечёткие знания

Операции (по Заде): дополнение μ_¬A = 1 − μ_A; пересечение μ_A∩B = min(μ_A, μ_B); объединение μ_A∪B = max(μ_A, μ_B).

Лингвистическая переменная — переменная, значениями которой являются слова («температура» = {низкая, средняя, высокая}); каждый терм — нечёткое множество с функцией принадлежности. Функции принадлежности строят по экспертным оценкам (прямое оценивание, парные сравнения) — обычно треугольные или трапециевидные.

Нечёткий вывод по обобщённому modus ponens: правила «ЕСЛИ x есть A ТО y есть B» с нечёткими посылками; этапы — фаззификация входов → вычисление степени истинности посылок (min/произведение) → агрегация заключений (max) → дефаззификация (например, центр тяжести). Так в ЭВМ представляют и обрабатывают нечёткие знания экспертов.

Модификаторы термов — арифметика над функциями принадлежности, имитирующая слова-усилители: «очень A» — концентрирование μ² (принадлежность падает у всех, кроме ядра), «более-менее A» — растяжение √μ. Так из базовых термов строятся производные значения лингвистической переменной без новых экспертных опросов.

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

Мамдани против Сугено. В алгоритме Мамдани заключения правил — нечёткие множества («обороты большие»), итог агрегируется и дефаззифицируется — наглядно, «по-человечески». В алгоритме Сугено заключение каждого правила — число или линейная функция входов (y = a·t + b), а итог — взвешенное среднее заключений по степеням активации правил: дефаззификация не нужна, вычисления дешевле, удобно для автоматической настройки коэффициентов по данным (нейро-нечёткие системы ANFIS). Мамдани выбирают за интерпретируемость, Сугено — за скорость и обучаемость.

Модели поиска решений

• Прямая цепочка рассуждений (от данных к цели): просматриваются правила, посылки которых подтверждены фактами; их заключения добавляются в рабочую память — пока не будет получена цель. Хороша, когда данных мало, а гипотез много.
• Обратная цепочка (от цели к данным): выдвигается гипотеза-цель; ищутся правила, её выводящие; их посылки становятся подцелями — пока подцели не сведутся к известным фактам или вопросам пользователю. Хороша при небольшом числе возможных целей (диагностика).
• Поиск в пространстве состояний — граф «состояние → действия»: перебор в глубину/в ширину, эвристический поиск (A*); при больших пространствах — редукция задачи на подзадачи.

Слепые стратегии поиска в пространстве состояний. Поиск в ширину раскрывает вершины слоями от старта: гарантированно находит кратчайший (по числу шагов) путь, но хранит весь фронт — память растёт как b^d (b — ветвление, d — глубина). Поиск в глубину идёт по одной ветке до упора с возвратами (бэктрекинг): памяти нужно всего O(b·d), но кратчайшесть не гарантируется, а на бесконечных ветках он «проваливается» — лечится ограничением глубины и итеративным углублением (глубина 1, 2, 3, … — сочетает экономность глубины с полнотой ширины).

Эвристический поиск. Эвристика h(x) — оценка стоимости пути от состояния x до цели. Алгоритм A* раскрывает вершины в порядке f(x) = g(x) + h(x), где g — фактическая стоимость пути от старта. Если эвристика допустима (не завышает истинное расстояние), A* находит оптимальный путь, просматривая лишь малую часть пространства. Пример: для игры в «восьмерку» (сдвиг костяшек 3×3) допустимые эвристики — число костяшек не на месте или сумма манхэттенских расстояний костяшек до целевых позиций; вторая «умнее» (ближе к истине) — и перебор меньше. Компромисс скорости и качества — жадный поиск только по h(x): быстрый, но без гарантий.

Редукция задач и И/ИЛИ-графы. Вторая модель поиска: цель разбивается на подзадачи. ИЛИ-вершина — альтернативные способы решить задачу (достаточно решить одну ветвь), И-вершина — совокупность подзадач, решить которые нужно все. Решение — поддерево, «закрывающее» корень: у ИЛИ-вершин выбрана одна ветвь, у И-вершин взяты все. Обратная цепочка рассуждений в ЭС — в точности поиск на И/ИЛИ-графе: правило с несколькими условиями в посылке порождает И-вершину, несколько правил с одним заключением — ИЛИ-вершину.