Болжолдуу ката

Графиги $f(x)=e^x$ (көк) анын сызыктуу жакындыгы менен $P_1(x)=1+x$ (кызыл) a = 0. Жакындоо катасы ийри сызыктардын ортосундагы ажырым болуп саналат жана ал 0дөн ары x маанилери үчүн көбөйөт.

Берилиштер маанисиндеги жакындатуу (болжолдуу) катасы - бул так маани менен ага кээ бир жакындаштыруунун ортосундагы дал келбөө. Бул ката абсолюттук ката (айласыздыктын сандык суммасы) же салыштырмалуу ката (маалыматтын маанисине бөлүнгөн абсолюттук ката) катары көрсөтүлүшү мүмкүн.

Компьютердик машинанын тактыгы же өлчөө катасы болжолдоо каталарынын эки жалпы себеби болуп саналат (мисалы, узундугу 4,53 см болгон кагаз, бирок сызгыч аны жакынкы 0,1 смге чейин баалоого гана мүмкүнчүлүк берет, андыктан аны 4,5 см деп өлчөйсүз).

Сандык туруктуулук-сандык анализдин математикалык чөйрөсүндө Алгоритмдин киргизүүсүндөгү каталар Алгоритмдин чыгаруусунда чоң каталарга алып келүүчү деңгээл; сандык туруктуу алгоритмдер киргизүү туура эмес калыптанганда чыгарууда олуттуу ката кетирбейт жана тескерисинче.

Формалдуу аныктама

Кээ бир v маанисин эске алып, биз v _{болжолдуу} v абсолюттук катасы ε >0 болсо менен жакындайт деп айтабыз.

$|v-v_{\text{approx}}|\le \epsilon$

мында вертикалдык тилкелер абсолюттук маанини билдирет.

Биз v _{болжолдуу} v болжолдуу салыштырмалуу ката η >0 болсо деп айтабыз

$|v-v_{\text{approx}}|\le \eta \cdot v$

.

Эгерде v ≠ 0 болсо, анда

$\eta =\frac{ϵ}{|v|}=\left|\frac{v-v_{\text{approx}}}{v}\right|=|1-\frac{v_{\text{approx}}}{v}|$ .

Процент катасы (салыштырмалуу катанын туюнтмасы)

$\delta =100\mathrm{\%}\times \eta =100\mathrm{\%}\times \left|\frac{v-v_{\text{approx}}}{v}\right|.$

Чектелген ката – бул жакындоо катасынын салыштырмалуу же абсолюттук өлчөмүнүн жогорку чеги.

Мисалдар

Калып:Diophantine approximation graph.svgМисал катары, эгерде так маани 50 жана жакындоо 49,9 болсо, анда абсолюттук ката 0,1 жана салыштырмалуу ката 0,1/50 = 0,002 = 0,2%. Практикалык мисал катары, 6 өлчөөдө мл стакан, мааниси 5 болду мл. Туура окуу 6 мл, бул конкреттүү кырдаалда пайыздык катаны билдирет, тегеректелген, 16,7%.

Сандардын ар кандай өлчөмдөгү жакындатууларын салыштырууда салыштырмалуу ката көп колдонулат. Мисалы, 3 абсолюттук катасы бар болжол менен 1000 адам, адатта, 3 абсолюттук катасы бар болжол менен 1000000 адамга караганда алда канча начар; биринчисинде салыштырмалуу ката 0,003 болсо, экинчисинде 0,000003 гана.

Салыштырмалуу катанын эки өзгөчөлүгү бар, аларды эске алуу керек. Биринчиден, чыныгы маани нөлгө барабар болгондо, салыштырмалуу ката аныкталбайт (төмөндө караңыз). Экинчиден, салыштырмалуу ката катыш шкаласында өлчөнгөндө гана мааниге ээ болот, (б.а. чыныгы мааниге ээ нөлгө ээ шкала), антпесе, ал өлчөө бирдиктерине сезгич болот. Мисалы, Цельсий шкаласында берилген температураны өлчөөдөгү абсолюттук ката 1 болгондо °C, жана чыныгы мааниси 2 °C, салыштырмалуу ката 0,5. Бирок так ушундай эле жакындоо Келвин шкаласы менен жасалса, 1 K абсолюттук катасы 275.15 бирдей чыныгы мааниси менен K = 2 °C 3,63 Калып:E салыштырмалуу ката берет.

Салыштыруу

Салыштырмалуу каталар боюнча ырастоолор туруктуу кошулууга дуушар болот, бирок константалар менен көбөйтүлбөйт. Тескерисинче, абсолюттук каталар туруктуу кошумчалоого сезгич эмес, бирок туруктуу көбөйтүүгө сезгич эмес.

Чыныгы сандардын полиномдук-убакыт жакындоосу

Эгерде ар бир ε >0 рационалдык саны үчүн, абсолюттук катасы ε менен v _{болжолдуу} рационалдык санын эсептөө мүмкүн болсо , көлөмү боюнча убакыттын полиномиясы боюнча v реалдуу маанисин киргизүүдөн абсолюттук ката менен полиномиялык эсептөөгө болот деп айтабыз. киргизүүнүн жана ε коддоо өлчөмү (бул O(log(1/ ε )). Окшош түрдө, v полиномдуу түрдө салыштырмалуу ката менен эсептелинет, эгерде ар бир η >0 рационалдык саны үчүн, киргизүүнүн өлчөмү жана коддоо өлчөмү боюнча убакыт полиномунда салыштырмалуу катасы η менен v _{болжолдуу} v рационалдуу санын эсептөө мүмкүн болсо. η .

Эгерде v салыштырмалуу ката менен полиномдуу эсептелсе (REL деп аталган кээ бир алгоритм боюнча), анда ал абсолюттук ката менен да полиномиялык жактан эсептелүүчү болот. Proof . ε >0 каалаган абсолюттук ката болсун. Биринчиден, салыштырмалуу ката менен REL колдонуңуз η= 1/2; рационал санын тапкыла r ₁ ушундай | v - r ₁ | ≤ | v |/2, демек |v| ≤ 2 | r ₁ |. Эгерде r ₁ =0 болсо, анда v =0 жана биз бүттүк. REL көп мүчө болгондуктан, r ₁ коддоо узундугу киргизүүдө көп мүчө болуп саналат. Эми, салыштырмалуу ката η=ε/ (2 |r ₁ |) менен RELди кайра иштетиңиз. Бул | канааттандырган r ₂ рационалдуу санын берет v - r ₂ | ≤ ε|v | / (2 r ₁ ) ≤ ε, ошондуктан ал каалагандай абсолюттук ката ε бар.  : 34 

Тескери маани, адатта, туура эмес. Бирок, эгерде биз |v| боюнча кандайдыр бир оң төмөнкү чекти деп ойлосок полиномдук убакытта эсептелиши мүмкүн, мисалы | v | > b > 0, жана v абсолюттук ката менен полиномиялык жактан эсептелүүчү (АБС деп аталган кээ бир алгоритм боюнча), анда ал салыштырмалуу ката менен да полиномиялык жактан эсептелүүчү болот, анткени биз жөн гана абсолюттук катасы бар ABS ε = η b деп атай алабыз.

Ар бир рационалдуу сан үчүн η >0 рационалдуу саны v _{болжолдуу} эсептей турган алгоритм η салыштырмалуу катасы бар v болжолдуу, киргизүүнүн өлчөмү боюнча убакыт полиномунда жана 1/ η (log(1/ η ) эмес), FPTAS деп аталат.

Инструменттер

Көпчүлүк көрсөтүүчү аспаптардын тактыгы толук масштабдагы окуунун белгилүү бир пайызынын чегинде кепилденет. Чектөөчү каталар, ошондой эле кепилдик каталары деп аталат, бул берилген маанилерден четтөө боюнча жогорку чектер.

Жалпылоо

аныктамалар качан учурга чейин узартылышы мүмкүн $v$ жана $v_{\text{approx}}$ абсолюттук маанини <i id="mwtw">n</i> -норма менен алмаштыруу менен <i id="mwtQ">n</i> -өлчөмдүү векторлор болуп саналат.

Ошондой эле караңыз

• Кабыл алынган жана эксперименталдык маани
• Шарт номери
• Статистикадагы каталар жана калдыктар
• Эксперименттик белгисиздик анализи
• Машина эпсилон
• Өлчөө ката
• Өлчөөнүн белгисиздиги
• Белгисиздикти жайылтуу
• Кванттоо катасы
• Салыштырмалуу айырма
• Тегерек ката
• Белгисиздик

Шилтемелер

1. Калып:Cite web
2. Калып:Cite web
3. Калып:Cite web
4. Калып:Cite web
5. Калып:Cite Geometric Algorithms and Combinatorial Optimization
6. Helfrick, Albert D. (2005) Modern Electronic Instrumentation and Measurement Techniques. p. 16. Калып:ISBN
7. Калып:Cite book

Тышкы шилтемелер

• Weisstein, Eric W. "Percentage error". MathWorld.