Comments 58
вообще не требует никаких знаний математики
Эм… ну да, фигня, начальная школа.
Как же все относительно в мире.
Я довольно востребованный прикладной программист с большим опытом. Но без образования и знаний математики. И с этой точки зрения статья обманула мои ожидания фразой «вообще не требует знаний».
Возможно вы учились в очень классной школе. Но мне кажется, вы переоцениваете уровень седьмого и десятого классов.
На всю статью вообще одна формула:
Я убеждён, что для того, чтобы понять, что происходит в математике, равно как и в программировании, нужно внимательно читать текст не один раз, и запускать весь код, изменяя входные параметры. Именно поэтому я не просто развожу руками в воздухе, но даю вполне конкретные куски исполняемого кода и сопровождающие картинки.
На лирическое отступление из этой статьи, нужно потратить минут 5.
Подавляющее число задач не связаны с математикой вообще никак. CRUD и бизнес-логика редко требуют сложных вычислений. А вот знания 100500 библиотек на все случаи жизни, умение писать простой и понятный код (поддерживаемый), умение расставлять приоритеты, изучать постоянно что-то новое — нужно всегда.
Программисты решают задачи бизнеса. Если задача решается с приемлемым качеством и в приемлемый срок — он профи.
Если появится проблема, требующая знаний — получить эти знания или нанять человека, специализирующегося на них — не проблема.
Ставить ярлык "говнокодер" я бы не стал, если человек не умеет в диффуры.
И я все-таки не утверждаю что каждый программист-неуч обязательно говнокодер. Хороший программист не обязан обладать знаниями Д. Кнута чтобы быть действительно хорошим программистом. Скорее всего, примеры таких программистов все же есть. Но, повторяю, чтобы утверждать что код, написанный неучем, действительно хороший, нужно какая-то точка отсчета. И желательно, чтобы оценку качества проводили не такие же неучи.
Общая задача — N неизвестных чуть выше уровень…
Они решают 2-3 неизвестных, без обобщений на n неизвестных. Так прописано в библии по подготовке к ЕГЭ. Им больше 3 и не надо…
Они в ступор встают, когда им пишешь что-то типа «а в степени n, где n=3»…
/* Задаём матрицу с данными */
M:matrix([-1, -0.5], [0, 0], [1, 0.5], [2, 0.9], [3, 1]);
/* Модель: U - переменная, A, B, C - неизвестные параметры */
f(U,A,B,C):=A*exp(B*U)+C*U^2;
/* Загружаем модуль пакета для МНК */
load(lsquares);
/* Вызываем реализацию МНК в пакете */
klist:lsquares_estimates(M, [U,I], I=f(U,A,B,C), [A,B,C]);
/* Подставляем найденные параметры в модель */
I(U):=float(ev(f(U,A,B,C), klist));
/* Определяем коэффициент детерминации R^2. Сначала найдём среднее значение */
mny:0;
for i:1 thru length(M) step 1 do mny:mny+M[i,2];
mny:mny/length(M);
/* Находим суммы квадратов */
sum1:0;
sum2:0;
for i:1 thru length(M) step 1 do (sum1:sum1+(M[i,2]-I(M[i,1]))^2, sum2:sum2+(M[i,2]-mny)^2);
/* Вычисляем до целой части коэффициент R^2 и выводим его */
Rsq:round((1-sum1/sum2)*100)$
printf(true, "R^2 = ~d%", Rsq)$
/* Сформируем из матрицы M список точек */
plist:create_list(M[k], k, 1, length(M));
/* Строим график */
plot2d([['discrete,plist], I(U)], [U, -1, 4], [style, [points, 2, 1, 1], lines], [color, red, blue]);
Я не так давно для одной модели использовал в Maxima не lsquares_estimates, а решал экстремальную задачу на минимум суммы квадратов остатков модели (модуль lbfgs — метод Бройдена-Флетчера-Гольдфарба-Шанно). lsquares_estimates умеет определять линейность модели относительно неизвестных параметров. Если линейность имеет место, получаемую нормальную систему линейных уравнений пакет решает аналитически (ответ в обыкновенных дробях выдаёт), иначе вызывает численное решение экстремальной задачи указанным методом. При этом не всегда удачно подбирает начальное приближение к решению. Надо как-нибудь сюда статью об этом написать.
maxima_tempdir:"d:\\";
Если экспериментальных данных много, забивать их списком долго (например, переносить из Excel). В Maxima есть возможность чтения данных в матрицу из текстового файла:
M:read_matrix("d:\data.txt");
Файл data.txt выглядит просто (без пустой строки в конце):
-1 -0.5
0 0
1 0.5
2 0.9
3 1
Если Maxima не может прочитать существующий файл, то попробуйте в пути к файлу наклонить слэш в другую сторону (как /).
Если встроенный МНК не идёт, то, как я писал, нужно решать задачу на минимум суммы квадратов:
/* Формируем выражение для суммы квадратов остатков модели */
delta:0$
for i:1 thru length(M) step 1 do delta:delta+(M[i,2]-f(M[i,1],A,B,C))^2;
s(A,B,C):=''delta$
/* Загружаем модуль пакета для экстремальной задачи на минимум */
load(lbfgs);
/* Ищем минимум ошибки модели */
klist:lbfgs(s(A,B,C),[A,B,C],[1,1,1],1e-6,[1,1]);
Как видно из кода, кое-где вместо ; стоит $, чтобы пакет не дублировал вывод длинных формул при большом объёме экспериментальных данных или длинной формуле для модели.
Математика без пояснения на бытовых примерах очень сложна для восприятия большинству. И каждый пример должен быть подкреплён практическим использованием. В Вашем случае любопытные примеры получились.
import cv2
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
#tracing the chief with OpenCV
im = cv2.imread('lenin_bw.png')
im = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY)
ret, thresh = cv2.threshold(im, 0, 255, 0)
im2, c, hierarchy = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_TC89_KCOS)
xs, ys = c[0][:, :, 0], c[0][:, :, 1]
xs, ys = [x.transpose()[0].tolist() for x in [xs, ys]]
y_max = max(ys)
ys = [y_max - y for y in ys]
#laplacian smoothing
def smooth_ex1(X):
return [(m[0] + m[2])/2 for m in zip([X[-1]] + X, X, X[1:] + [X[0]])]
#animated plot of the results
fig, ax = plt.subplots()
ln, = plt.plot(xs, ys, animated = True)
def init():
plt.axis('equal')
return ln,
def update(frame):
global xs, ys
xs = smooth_ex1(xs)
ys = smooth_ex1(ys)
ln.set_data(xs + [xs[0]], ys + [ys[0]])
return ln,
ani = FuncAnimation(fig, update, init_func = init, blit = True)
plt.show()
Профиль первого попавшегося на Яндексе Ильича в профиль, трэйсил контур через OpenCV, к теме не особо относится, но для полноты картины пусть будет:
У кого нет OpenCV — можно выкинуть всё до комментария про laplacian smoothing и вместо этого захардкодить готовый контур:
xss = [282, 282, 277, 274, 266, 259, 258, 249, 248, 242, 240, 238, 240, 239, 242, 242, 244, 244, 247, 247, 249, 249, 250, 251, 253, 252, 254, 253, 254, 254, 257, 258, 258, 257, 256, 253, 253, 251, 250, 250, 249, 247, 245, 242, 241, 237, 235, 232, 228, 225, 225, 224, 222, 218, 215, 211, 208, 203, 199, 193, 185, 181, 173, 163, 147, 144, 142, 134, 131, 127, 121, 113, 109, 106, 104, 99, 95, 92, 90, 87, 82, 78, 77, 76, 73, 72, 71, 65, 62, 61, 60, 57, 56, 55, 54, 53, 52, 51, 45, 42, 40, 40, 38, 40, 38, 40, 40, 43, 45, 45, 45, 43, 42, 39, 36, 35, 22, 20, 19, 19, 20, 21, 22, 27, 26, 25, 21, 19, 19, 20, 20, 22, 22, 25, 24, 26, 28, 28, 27, 25, 25, 20, 20, 19, 19, 21, 22, 23, 25, 25, 28, 29, 33, 34, 39, 40, 42, 43, 49, 50, 55, 59, 67, 72, 80, 83, 86, 88, 89, 92, 92, 92, 89, 89, 87, 84, 81, 78, 76, 73, 72, 71, 70, 67, 67]
yss = [0, 76, 81, 83, 87, 93, 94, 103, 106, 112, 117, 124, 126, 127, 130, 133, 135, 137, 140, 142, 143, 145, 146, 153, 156, 159, 160, 165, 167, 169, 176, 182, 194, 199, 203, 210, 215, 217, 222, 226, 229, 236, 240, 243, 246, 250, 254, 261, 266, 271, 273, 275, 277, 280, 285, 287, 289, 292, 294, 297, 300, 301, 302, 303, 301, 301, 302, 301, 303, 302, 300, 300, 299, 298, 296, 294, 293, 293, 291, 288, 287, 284, 282, 282, 280, 279, 277, 273, 268, 267, 265, 262, 260, 257, 253, 245, 240, 238, 228, 215, 214, 211, 209, 204, 203, 202, 200, 197, 193, 191, 189, 186, 185, 184, 179, 176, 163, 158, 154, 152, 150, 147, 145, 142, 140, 139, 136, 133, 128, 127, 124, 123, 121, 117, 111, 106, 105, 101, 94, 92, 90, 85, 82, 81, 62, 55, 53, 51, 50, 48, 48, 47, 47, 48, 48, 49, 49, 51, 51, 53, 54, 54, 58, 59, 58, 56, 56, 55, 54, 50, 48, 46, 44, 41, 36, 31, 21, 16, 13, 11, 7, 5, 4, 2, 0]
"… данная процедура сходится к истинному решению" — подобная фраза просто находка для экзаменатора по математике.
47 миллионов результатов.
подобная фраза просто находка для экзаменатора по математике
Что-то мне кажется, что это не очень хорошая находка для экзамена. Или хорошая находка для не очень хорошего экзаменатора.
1000 явлется решением системы x=0
Я лишь хотел вас подвести к мысли о том, что система сама по себе решений не имеет. Решают задачи, а не уравнения. А когда мы договоримся про то, какую задачу решали, тогда можно будет договариваться про прилагательные рядом со словом решение.
Скажите, вы когда-либо преподавали студентам? Вы считаете, что задача экзаменатора это "построить логическую беседу на тему"? Это, возможно, задача при проведении семинара, но вряд ли при проведении экзамена.
Я не знаю, как вы себе это представляете, но у меня перед глазами встает такая картина. Экзамен. Студент, волнуясь, рассказывает про решение СЛАУ, и тут экзаменатор, который до этого слушал его с несколько скучающим видом, вскидывается и, едва пряча ехидную улыбку, спрашивает: так-так-так, голубчик! Вот вы говорите — истинное решение, да? Расскажите-ка, а почему же оно "истинное"? И какие такие не истинные бывают?
Жуткая картинка, на самом деле.
Формула
f[i] = (f[i-1] + f[i+1])/2
вроде бы как предполагает локальное (зависящее лишь от ближайших соседей) и симметричное преобразование, но приведенный алгоритм реализует нечто другое.Если предположить, что в начале очередной итерации
f = [f0, f1, f2, ..., f31]
, то проделав несколько шагов итерации вручную, видно, что при этом происходят следующие замены: f0 -> f1
f1 -> (f0+f2)/2 == (f1+f2)/2
f2 -> (f1+f3)/2 == (f1+f2+2*f3)/4
f3 -> (f2+f4)/2 == (f1+f2+2*f3+4*f4)/8
f4 -> (f3+f5)/2 == (f1+f2+2*f3+4*f4+8*f5)/16
...
f30 -> (f29+f31)/2 == (f1+f2+2*f3+4*f4+...+(2**29)*f31)/(2**30)
f31 -> f30 == (f1+f2+2*f3+4*f4+...+(2**29)*f31)/(2**30)
Это преобразование 1) нелокальное (все значения зависят от f1, хоть и с экспоненциально убывающим коэффициентом); 2) асимметричное (значения с большими индексами зависят от всех значений с меньшими индексами, но обратное неверно); 3) от f0 вообще ничего не зависит.
Да, при этом некое «сглаживание» несомненно происходит (с каждой итерацией значения всё меньше отличаются), но то ли это сглаживание, которое имелось в виду?
Кстати, внимательный читатель должен был бы заметить, что, строго говоря, у меня в коде системы линейных уравнений решаются не методом Якоби, но методом Гаусса-Зейделя
Ну вот вы и есть тот самый внимательный читатель :)
Сравните имплементации метода Якоби и метода Гаусса-Зейделя.
А вот так выглядит первая итерация обоих методов:
Гаусс-Зейдель:
в названии статьи присутствуют наименьшие квадраты. Увидели ли вы их в тексте?Скажу честно — не увидел. Зато увидел свёртку.
Методы наименьших квадратов без слёз и боли