|
Главная -> Справочник по алгоритмам 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 [46] 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 d*= I xf(/„ fe=0, 1,2..... (5.27) Полином (5.25) степени m<.N, где N - число nap Xi и yi, обеспечивает аппроксимацию (и интерполяцию) таблично заданной функции yi {Xi) с минимальной среднеквадратичной погрешностью . - * 1 = 1 (5.28) Если m = N, то имеет место обычная интерполяция, т. е. значения у (х) (5.25) при х=х, точно совпадают с заданными {/,-. При tiKCN такого совпадения в общем случае нет. Таким образом, аппроксимация у, (х,) по методу наименьших квадратов имеет более универсальный характер, чем обычная интерполяция (§ 4.2). Если достаточно ограничиться вычислением лишь коэффициентов ао, ai, ..., От полинома (5.25) без вычисления значения Е, то нет необходимости в хранеиии массивов X, и yi. При этом достаточно вычислить с. (массив из 2т чисел) и dk (массив из m чисел) с помощью (5.26) и (5.27) и решить полученную систему линейных уравнений методом Гаусса (см. § 4.1). Таким образом, составлена программа 5.25. Помимо вычисления коэффициентов ао, at, .... am она обеспечивает нахождение у (х) по заданному X с помощью полученного полинома (5.25). Программа 5.25. Пример. Используем пример к программе 5.24 (задаем т=М = 2 и n~N=7). Получим следующий результат: ао=Л(0) = =3, а\=А(\)=0,А и *2=/Ч(2) = -0,01. Задав далее х = 7, получаем у (x) = Y {Х) = =5,31. Время счета контрольного примера (без учета времени ввода х,- и yt) около 7 с. Полиномиальная регрессия (аппроксимация) с автоматическим выбором степени полинома выполняется по следующему алгоритму. Вначале задается степень т = 1 (линейная регрессии). Отсчеты х,-, yi вводятся и запоминаются. После нахождения всех (вначале ао и ci) с помощью (5.28) вычисляется среднеквадратичная погрешность Е и сравииваетси с заданной £1. Если £> £1, степень полинома m увеличивается на 1, и т. д. Счет прекращается, как только достигается £<;£i. В программе 5.26 наряду с этим алгоритмом возможна реализация алгоритма вычислении коэффициентов со, ai. . .... Qm полинома заданной степенью m с вычислением получаемой при этом погрешности £. Обеспечивается также вычисление у (х) по заданному х. Для повышения точности система уравнений для вычисления Со. а...... От решаетси методом Гаусса с выбором главного элемента. Программа 5.25. 05 PRINTАППРОКСИМАЦИЯ ПОЛИНОМОМ ПО МЕТОДУ НАИМЕНЬШИХ КВАДРАТОВ 10 1НРиТВВЕДИТЕ СТЕПЕНЬ ПОЛИНОМА M=n:LETH=n+1 £0 DIM ai:h,h)b«:h>/C«:2*h),Xi:h> 30 INPUTBBEAHTE ЧИСЛО ПАР X..V N=H 40 FOR 1=1 TO H!PRINT!3.6!ДЛЯ I=I;INPUTBBEAHTE X,V x,v 45 LETF=l!FOR J=l TO £*h-lsIF J>h THEN 55 50 LETB<:J)=E<J>+V5LETV=V*X 55 LETC<J>=C<J>+F:LETF=F*X!HEXT JsNEXT I 60 FOR 1=1 TO N:LETK=I!FOR J=l TO N 65 LETAafJ>=C«:K>!LETK=K+ls№XT J:NEXT I 70 FOR 1=1 TO N-l!FOR J=I+1 TO N 75 LETAiJ,I>=-A«:j,I)>A<bI>:FOR K=I+1 TO N 80 LETA<JK>=ft«:j,K>+A<J,I>!t!A(bK>! NEXT К 90 LETB<:j>=B<:j)+A<:j,i>jitB<i)! next j: next I 100 LETX<N>=B<N>/A<N,N> 110 FOR I=N-1 TO 1 STEP -is LETH=B<I> 120 FOR J=I+1 TO NS LETH=H-X<J>»;A<bJ>sNEXT J 130 LETXa>=HA<bn:NEXT I 140 PRINTКОЭФФИЦИЕНТЫ ПОЛИНОМА 158 FOR 1=0 TO N-lsPRlHT!3.0!A<I>=!F1.9!Xa+l>!NEXT I 160 INPUTBBEAHTE X=ZsLETS=0sFOR I=N TO 2 STEP -1 170 LETS=<S+Xa>>«ZsNEXT I 188 PRINTЗНАЧЕНИЕ VCX>=!F1.9!S+X<l)sG0T0 168sEND СоСо+СЮ!+C2as+ ... +Cmam = do, Ctan + C2ai+C3a2+ ... +Cm+\am-di, CmCfl + Cm + tai+Cm+2a2+ •.• +C2„am-dm, Ci== X! xi, /=0, 1, 2, .... 2m, (5.26) 1=1 Пример. Используем пример, приведен- Линейное сглаживание по трем точкам ный к программе 5.24. Так, если задать реализуется с помощью следующих формул: £= 1 • 10~ программа (после примерно 1 мин - /с , о \ ,п счета) выдаст: М = 2, £ = 0, /4(0) =3, Уо-(byo + ly-yi)/6, (1) =0,4, Л(2) = -0,01 и У(Х)=Ъ,3\ при fe-1+№ + </;+i)/3, I</<W-1, X = 7. Время счета существенно больще, Af = (5(/л/ + 2(/л/-1 -Ул/-2)/6, чем по программе 5.25, в связи с вычисле- нием £ и автоматическим выбором степени где N - номер последней точки (ордина- полинома т. ты yi). Программа 5.27. 6 5.7. Сглаживание данные экс- Пример сглаживания дан в табл. 5.2. перимента Линейное сглаживание по 5 точкам проводится с использованием формул - Сглаживание данных эксперимента яв- У"-(3№ + 2у.+(/.-(/4)/5, ляется специальной операцией усреднения - (4{/o+3i/i--2(/2 + (/.з)/10, с помощью интерполяционных полиномов, =te-2+№-i4-( + (/,+ p+y;+2)/5, обеспечивающей получение уточненного зна- 2-<i-<W -2 чения у, по заданному значению у, и ряду . - lo,, , о„ "",7" w. близлежащих значений (...), <У>-з + 2Ул/ 2 + 3</л/ i +4{/,v)/10, известных со случайной погрещностью. yN=iyN + yN-i+yN~2-yN-i)/- le РК1НТ-"йППР0КСИМАииЯ ПОЛЖОМОТ по МЕТОЛУ HAMMEHbiJlJ-iX КВАДРАТОВ 15 PRIHTC ВОЗМОЖНОСТЬ» АВТОМАТИЧЕСКОГО ВЫБОРА СТЕПЕНИ ПОЛИНОМА ге INPUTЗАДАЙТЕ ЧИСЛО УЗЛОВ ИНТЕРПОЛЯЦИИ N=4 35 DIM X<H),VCH),ZCH>/B<H>/G<H)/A<H/H)/C«:h.H>.B<S*H) 38 FOR 1=1 то Н: PRINTIS,8!ВВЕДИТЕ XlfVI 35 INPUT X<I>,V<I>s NEXT I: LET N=1 48 PRINTУКАЖИТЕ 8-ЕСЛИ ЗАДАНА ПОГРЕШНОСТЬ ИНТЕРПОЛЯЦИИ 58 INPUT* 1-СТЕПЕНЬ ПОЛИНОМА U:IF U=9 GOTO 88 66 INPUTЕЕЕДИТЕ СТЕПЕНЬ ПОЛИНОМА M<N M=N5&0T0 85 88 ШРиТЗАДАйТЕ СРЕДНЕКВАДРАТИЧНУЮ ПОГРЕШНОСТЬ Е1=Е1 85 LET N=N+ls FOR J=0 TO ЗжН-и IF J>N GOTO 95 98 LET B<J>=8 95 LET ]r<J>=e! NEXT Js FOR 1=1 TO И: LET Ri=V<I):LET F=l .185 FOR J=l TO 2!i!N-l: IF J>N GOTO 115 lie let B<J>=B<:J>+R! LET R=R*Xa> 115 LET D<J>=D<J>+F! LET F=Fii!X<:i): NEXT J: NEXT I 128 FOR 1=1 TO Ns LET K=I: FOR J=l TO N 138 LET A<I,J>=D<K)s LET K=K+1! NEXT Js NEXT I . . 140 LET Nl=N-ls FOR K=l TO N1 150 IF abs<A<K/K>>>0 GOTO 238 168 LETKl=K+l:FOR M=K1 TO N: IF ABS<A<M/K))=0 GOTO S18 190 FOR L=l TO N: LET U=A<K,L>! LET A<K,L>=A<M/L) 280 LET A<M,L>=U: NEXT L 210 NEXT M 220 LET u=b<:k>! let b<k)=b<m>! let B<M>=U 238 LET 6<K)=B<K)-A<:k,K>: LET K1=K+1 240 FOR I=K1 TO N! LET B<I>=Ba>-A<r/K>!«i<K) 258 FOR J1=K TO NS LET J=N~J1+K5 LET C<K»J)=A«:K,J)/A<K»K) 260 LET A<bJ>=A<bJ>-A<bK)!(iCCK,J>!NEXT JlsNEXT Is NEXT К 280 LET M=Ns LET Z«:M)=B<M>/A<M,M) 290 LET M=M-l: LET S=85 for L=M TO N1 308 LET S=S+C<M/L+l>!i!2<L+l>s NEXT L 310 LET 2<M)=G<M)-S! IF M>1 GOTO 298 320 LET E=es FOR 1=1 TO Hs LET S=V<I>s LET R=l 338 FOR J=l TO N! LET S=S-R3*Z«:J)! LET R=R!ifX<Os NEXT J 340 LET Е=Е+8жв!НЕХТ I:LET E=SQR«:E/H>s IF U=i GOTO 378 358 IF Е=<Ё1 GOTO 378 368 IF N<H goto 85 370 PRINTСТЕПЕНЬ ПОЛИНОМА M=N-1 388 PRINT!F1.9!ПОГРЕШНОСТЬ ИНТЕРПОЛЯЦИИ E=E!IF U=l GOTO 398 385 PRINTЕСЛИ E БОЛЬШЕ ЗАДАННОЙ»УВЕЛИЧЬТЕ N Н ПОВТОРИТЕ ВВОД 390 PRINT КОЭФФИЦИЕНТЫ ПОЛИНОМА 400 FOR 1=1 ТО N!PRINT!2.0!A<I-l>=!F1.9!2<n5NEXT I 410 1НРиТВВЕДИТЕ X=XsLETQ=0sFOR I=N ТО 2 STEP -1 420 LETQ=<Q+2<:i>)!t«sNEXT l!LETQ=Q+Za> 430 PRINTЗНАЧЕНИЕ V<X>=Q!GOTO 410SENB le РР1ЫТ!Р1.9!ЛННЕйН0Е СГЛАЙ1НВАНИЕ ПО 3 ТОЧКАМ 20 ШРиТВВЕДИТЕ НОМЕР ПОСЛЕДНЕЙ ТОЧКИ Ы=Н 30 PRINTBBEAHTE V 6sINPUT ft 48 PRINTВВЕДИТЕ V IsINPUT В 58 PRINTВВЕДИТЕ V 2:INPUT С • 60 PRINTSV 0=<5*ft+2*B-C>6 70 PRINTSV 1=<A+B+C>---3 80 FOR 1=2 TO N-l:LETA=B:LETB=C 90 PRINT!3.0!ВВЕДИТЕ V1+1=:IHPUT С 100 PRINT-SVI=!1.9!CA+B+C>/-3:NEXT I 110 Р1?1НТ!3.е!SVH= !F1.9U-A+2*B+5*C>.6 1-20 ENB Таблица 5.2 Результаты линейного сглаживания по 3 и 5 точкам {JV = 9)
Программа 5.28. 10 PRINTЛИНЕЙНОЕ СГЛАМИВАНИЕ ПО 5 ТОЧКАМ 28 INPUTВВЕДИТЕ НОМЕР ПОСЛЕДНЕЙ ТОЧКИ N=H 30 PRINTIF1.9!ВВЕДИТЕ V 8=!INPUT А 48 PRINTBBEAHTE V 1=sINPUT В 50 PRINTBBEAHTE V 2=sINPUT С 68 PRINTВВЕДИТЕ V 3=sIHPUT D 70 PRINTBBEAHTE V 4=г INPUT E 80 PRIhn-SV 0=<3*A+2!i!B+C-E).-5 98 PRINTSV 1=<4жА+ЗжВ+2жС+Е>10 lee PRINTSV £=<ft+B+C+Ii+E>/5 110 FOR 1=3 TO N-2 120 LETA=B: LETB=C: LETC=Ii! LETD=E 130 PRIHT!3.0!ВВЕДИТЕ V1+2=:IHPUT E 140 PRINTSV 1= !F1.9!<A+B+C+Ii+E>5 150 NEXT I 160 PRINT!3.0!SVN-1= !F1.9UB+2«C+3*D+"4*E>10 170 PRINT!3.0!SVN= !Р1.ЭК.ЗжЕ+£жЕ+С-А>/5 188 END Контрольный пример см. в табл. 5.2. Нелинейное сглаживание по семи точкам обеспечивает усреднение на основе примене-I ния полинома третьей степейи и реализуется применением формул Уо= (39i/o + 8(/i-4 {у2+уз - у*) +№-2(/б)/42, (/, = (8(/о+19yi + 16(/2 + 6(/3-4(/4-7i/5 + + 4(/7)/42, У2 = ( - 4(/П + 16(/, + 19(/2 + 12(/з + 2(/4 - 41/5 + +/б)/42. У,= (7(/, + 6 ((/,.+ ,+(/;. ,) +3 ((/, + 2 + (/,-.2) - -2 (у,+з + </,-з))/21, 3<i<W-3, yN-2= (i/AZ-e -4(/л/-5 + 2(/л/-4 f 12(/л/-з + + 19</w 2+ 16</л/- 1 -4</л/)/42, yN-i = (4(/л/-б -7(/л/-5 -4(/л/-4 +6(/л/-3 + +1 бул/-2 + 19(/л/-. 1 + 8</л/)/42, (/w=: (-2(/л,-б+41/л/-5+4л/-4-4</л/-з- -4г/л/-2 + 8</л/-1+39(/л/)/42. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 [46] 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 0.0185 |
|