Przejdź do nawigacji Przejdź do wyszukiwania
 10 Ten wikipedysta edytuje polskojęzyczną Wikibooks od 10 lat, 1 miesięcy i 24 dni.Obliczono 23 października 2019.
 pl Polski jest językiem ojczystym tego użytkownika.
 en-2 This user can read and write intermediate English.

Witam.

 Przydatne linki admin - import spr. - NPA

błędy w obliczeniach numerychnych

Avoiding loss of significance

Although the quadratic formula provides an exact solution, the result is not exact if real numbers are approximated during the computation, as usual in numerical analysis, where real numbers are approximated by floating point numbers (called "reals" in many programming languages). In this context, the quadratic formula is not completely stable.

This occurs when the roots have different order of magnitude, or, equivalently, when b2 and b2 − 4ac are close in magnitude. In this case, the subtraction of two nearly equal numbers will cause loss of significance or catastrophic cancellation in the smaller root. To avoid this, the root that is smaller in magnitude, r, can be computed as $(c/a)/R$ where R is the root that is bigger in magnitude.

A second form of cancellation can occur between the terms b2 and 4ac of the discriminant, that is when the two roots are very close. This can lead to loss of up to half of correct significant figures in the roots.

Roots of a quadratic (ax2 + bx + c)

If x1 ≈ 0 and x2 >> 0, then the quadratic formula is unstable.

Computing x2 by the quadratic formula and then setting x1 = cx2 / a is stable.

Innym przykładem na to, że nawet najprostsze algorytmy mogą być źle uwarunkowane jest „szkolny” algorytm obliczania pierwiastków równania kwadratowego

$x_{1}={\frac {-b-{\sqrt {b^{2}-4ac}}}{2a}}$ $x_{2}={\frac {-b+{\sqrt {b^{2}-4ac}}}{2a}}$ W sposobie obliczenia jednego z pierwiastków jest odejmowanie. Możliwa jest sytuacja, w której wartość $-b$ i ${\sqrt {b^{2}-4ac}}$ mogą być dość bliskie zeru co do modułu - nastąpi utrata cyfr znaczących.

Rozwiązanie Sposobem na ominięcie tego problemu mogą być Wzory Viète’a - dobrze uwarunkowany pierwiastek może być obliczony „wprost”, drugi otrzymany ze wzoru Viète’a. Należy również zauważyć, że możemy mieć tutaj tutaj do czynienia z dwoma przypadkami tj. b>=0 oraz b<0. Dla pierwszego przypadku dobrze uwarunkowanym będzie pierwiastek pierwszy, a dla drugiego przypadku dobrze uwarunkowanym będzie pierwiastek drugi.

Instability of the quadratic equation

For example, consider the quadratic equation

$ax^{2}+bx+c=0,$ with the two exact solutions:

$x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}.$ This formula may not always produce an accurate result. For example, when $c$ is very small, loss of significance can occur in either of the root calculations, depending on the sign of $b$ .

The case $a=1$ , $b=200$ , $c=-0.000015$ will serve to illustrate the problem:

$x^{2}+200x-0.000015=0.$ We have

${\sqrt {b^{2}-4ac}}={\sqrt {200^{2}+4\times 1\times 0.000015}}=200.00000015\dotso$ In real arithmetic, the roots are

$(-200-200.00000015)/2=-200.000000075,$ $(-200+200.00000015)/2=0.000000075.$ In 10-digit floating-point arithmetic:

$(-200-200.0000001)/2=-200.00000005,$ $(-200+200.0000001)/2=0.00000005.$ Notice that the solution of greater magnitude is accurate to ten digits, but the first nonzero digit of the solution of lesser magnitude is wrong.

Because of the subtraction that occurs in the quadratic equation, it does not constitute a stable algorithm to calculate the two roots.

A better algorithm

A careful floating-point computer implementation combines several strategies to produce a robust result. Assuming that the discriminant b2 − 4ac is positive, and b is nonzero, the computation would be as follows:

{\begin{aligned}x_{1}&={\frac {-b-\operatorname {sgn}(b)\,{\sqrt {b^{2}-4ac}}}{2a}},\\x_{2}&={\frac {2c}{-b-\operatorname {sgn}(b)\,{\sqrt {b^{2}-4ac}}}}={\frac {c}{ax_{1}}}.\end{aligned}} Here sgn denotes the sign function, where $\operatorname {sgn}(b)$ is 1 if $b$ is positive, and −1 if $b$ is negative. This avoids cancellation problems between $b$ and the square root of the discriminant by ensuring that only numbers of the same sign are added.

To illustrate the instability of the standard quadratic formula compared this formula, consider a quadratic equation with roots $1.786737589984535$ and $1.149782767465722\times 10^{-8}$ . To 16 significant digits, roughly corresponding to double-precision accuracy on a computer, the monic quadratic equation with these roots may be written as

$x^{2}-1.786737601482363x+2.054360090947453\times 10^{-8}=0.$ Using the standard quadratic formula and maintaining 16 significant digits at each step, the standard quadratic formula yields

${\sqrt {\Delta }}=1.786737578486707,$ $x_{1}=(1.786737601482363+1.786737578486707)/2=1.786737589984535,$ $x_{2}=(1.786737601482363-1.786737578486707)/2=0.000000011497828.$ Note how cancellation has resulted in $x_{2}$ being computed to only 8 significant digits of accuracy.

The variant formula presented here, however, yields the following:

$x_{1}=(1.786737601482363+1.786737578486707)/2=1.786737589984535,$ $x_{2}=2.054360090947453\times 10^{-8}/1.786737589984535=1.149782767465722\times 10^{-8}.$ Note the retention of all significant digits for $x_{2}$ .

Note that while the above formulation avoids catastrophic cancellation between $b$ and ${\sqrt {b^{2}-4ac}}$ , there remains a form of cancellation between the terms $b^{2}$ and $-4ac$ of the discriminant, which can still lead to loss of up to half of correct significant digits. The discriminant $b^{2}-4ac$ needs to be computed in arithmetic of twice the precision of the result to avoid this (e.g. quad precision if the final result is to be accurate to full double precision). This can be in the form of a fused multiply-add operation.

To illustrate this, consider the following quadratic equation, adapted from Kahan (2004):

$94906265.625x^{2}-189812534x+94906268.375.$ This equation has $\Delta =7.5625$ and roots

$x_{1}=1.000000028975958,$ $x_{2}=1.000000000000000.$ However, when computed using IEEE 754 double-precision arithmetic corresponding to 15 to 17 significant digits of accuracy, $\Delta$ is rounded to 0.0, and the computed roots are

$x_{1}=1.000000014487979,$ $x_{2}=1.000000014487979,$ which are both false after the 8-th significant digit. This is despite the fact that superficially, the problem seems to require only 11 significant digits of accuracy for its solution.

Przydatne strony

(Skopiowałem ze strony Karola Dąbrowskiego)

• <source lang="c">...</source>

zunzun

git add is a multipurpose command – you use it to begin tracking new files, to stage files, and to do other things like marking merge-conflicted files as resolved. I

git patch

How to contribute your changes (bug fixes, new features, ...):

git checkout master git pull git checkout -b my-new-stuff

1. edit files, make changes

git add your-changed-files git commit

1. write a short description, the first line is the most important

git format-patch master

1. then email the patches as attachments

Try to split each distinct set of changes into different commits (eg: a bug fix in one file and a new feature in another file should be two commits). On the other hand, changes in multiple files for the same bug-fix or feature should be in one commit. Make sure it compiles before you commit, and preferably make sure it runs and does the right things without breaking other stuff.

Alternatively to git format-patch and emailing, make your repository available online. https://gitorious.org has tools for forking repositories and submitting merge requests, though I've not used them much so can't offer any tips.

c

c= 1/4
zf= z = 0.499999996905453  +0.000000000000000 i
z = 0.503446319355695  +0.000195822466591 i
z = 0.501859335396733  +0.000051833858094 i
z = 0.504519704479711  +0.000098150630449 i

funkcje

• aint(x) returns the integral value between x and 0, nearest x.
• anint(x) returns the nearest integral value to x, except halfway cases are rounded to the integral value larger in magnitude.
• Nearest Integer Function = nint(x) converts x into int format rounding to the nearest int value, except halfway cases are rounded to the int value larger in magnitude.

c

tablice

• typ
• statyczne (
• dynamiczne (
• wymiar
• jednowymiarowe (1D , wektor)
• dwuwymiarowe ( 2D , macierz , ang. matrix)
• wielowymiarowe
• operacje na tablicach
• deklaracja
• initializacja
• użycie
• usunięcie
•  ???
• Flexible array member =
• variable-length array = VLA, runtime-sized

analiza programu w języku Haskell

-- Haskell code by Claude Heiland-Allen
-- http://mathr.co.uk/blog/

import Data.List (genericTake, genericDrop, intercalate)
import Data.Fixed (mod')
import Data.Ratio ((%), numerator, denominator)
import System.Environment (getArgs)

type InternalAngle = Rational

type ExternalAngle = ([Bool], [Bool])

pretty :: ExternalAngle -> String
pretty (pre, per) =  bits pre ++ "(" ++ bits per ++")"

bits :: [Bool] -> String
bits = map bit

bit :: Bool -> Char
bit False = '0'
bit True = '1'

binary :: [Bool] -> Integer
binary [] = 0
binary s = case readInt 2 (elem"01") (\c -> case c of '0' -> 0 ; '1' -> 1) (bits s) of
[(b, "")] -> b

rational :: ExternalAngle -> Rational
rational (pre, per) = (binary pre % 2^p) + (binary per % (2^p * (2^q - 1)))
where
p = length pre
q = length per

bulb :: InternalAngle -> (ExternalAngle, ExternalAngle)
bulb pq = (([], bs ++ [False, True]), ([], bs ++ [True, False]))
where
q = denominator pq
bs
= genericTake (q - 2)
. map (\x -> 1 - pq < x && x < 1)
. iterate (\x -> (x + pq) mod' 1)
$pq hub :: InternalAngle -> [ExternalAngle] hub pq = [ (sm, shift k sp) | k <- [0, b .. (q - p - 1) * b] ] ++ [ (sp, shift k sp) | k <- [(q - p) * b, (q - p + 1) * b .. (q - 1) * b] ] where p = numerator pq q = denominator pq (([], sm), ([], sp)) = bulb pq (ab, cd) = parents pq b = denominator ab shift k = genericTake q . genericDrop k . cycle -- parents :: InternalAngle -> (InternalAngle, InternalAngle) parents pq = go q 1 0 p 0 1 where p = numerator pq q = denominator pq go r1 s1 t1 r0 s0 t0 | r0 == 0 = let ab = - s1 % t1 a = numerator ab b = denominator ab c = p - a d = q - b cd = c % d in (min ab cd, max ab cd) | otherwise = let (o, r) = divMod r1 r0 s = s1 - o * s0 t = t1 - o * t0 in go r0 s0 t0 r s t main :: IO () main = do [sp, sq] <- getArgs p <- readIO sp q <- readIO sq let pq = p % q (lo, hi) = bulb pq hs = hub pq putStrLn$ "internal angle p/q = " ++ sp ++ " / " ++ sq
putStrLn $"internal angle in lowest terms = " print pq putStrLn$ "rays of the bulb:"
putStrLn $pretty lo ++ " = " ++ show (rational lo) putStrLn$ pretty hi ++ " = " ++ show (rational hi)
putStrLn $"" putStrLn$ "rays of the hub:"
forM_ hs $\h -> putStrLn$ pretty h  --- ++ " = " ++ show (rational h)
1. Szablon:Citation
2. Szablon:Citation
3. Szablon:Citation, Section 5.6: "Quadratic and Cubic Equations".
4. Szablon:Citation