「懸鉤子」的全部文章

數字派 NumPy ︰陣列運算‧《外傳二》APL ㄅ

事實上 Von Neumann 的計算機架構,對於電腦程式語言的發展,有著極為深遠的影響,產生了現在叫做 Von Neumann 程式語言,與Von Neumann 的計算機架構,同形 isomorphism 同構

program variables ↔ computer storage cells
程式變數 對映  計算機的儲存單元

control statements ↔ computer test-and-jump instructions
控制陳述 對映 計算機的『測試.跳至』指令

assignment statements ↔ fetching, storing instructions
賦值陳述 對映 計算機的取得、儲存指令

expressions ↔ memory reference and arithmetic instructions.
表達式 對映 記憶體參照和算術指令

John Warner Backus 曾經斷言,由於電腦圈長期過度強調 Von Neumann 的程式語言與計算機架構,已經產生了『惡性循環』,使得非此類的語言由於不符合經濟而日漸式微,比方 APL 語言 ── 註︰有興趣的,可以參照這裡在 Raspbian 上安裝 ──。

─── 《CPU 機器語言的『解譯器』

 

並非因 APL 不是

Von Neumann programming languages

A von Neumann language is any of those programming languages that are high-level abstract isomorphic copies of von Neumann architectures.[1] As of 2009, most current programming languages fit into this description[citation needed], likely as a consequence of the extensive domination of the von Neumann computer architecture during the past 50 years.

The differences between Fortran, C, and even Java, although considerable, are ultimately constrained by all three being based on the programming style of the von Neumann computer.[citation needed] If, for example, Java objects were all executed in parallel with asynchronous message passing and attribute-based declarative addressing, then Java would not be in the group.

The isomorphism between von Neumann programming languages and architectures is in the following manner:

  • program variables ↔ computer storage cells
  • control statements ↔ computer test-and-jump instructions
  • assignment statements ↔ fetching, storing instructions
  • expressions ↔ memory reference and arithmetic instructions.

 

亦無關乎 John Warner Backus 的

Criticism

John Backus asserted that assignment statements in von Neumann languages split programming into two worlds. The first world consists of expressions, an orderly mathematical space with potentially useful algebraic properties: most computation takes place here. The second world consists of statements, a disorderly mathematical space with few useful mathematical properties (structured programming can be seen as a limited heuristic that does apply in this space, though).

Backus[2] claimed that there exists now in computer science a vicious cycle where the long-standing emphasis on von Neumann languages has continued the primacy of the von Neumann computer architecture, and dependency on it has made non-von Neumann languages uneconomical and thus limited their further development: the lack of widely available and effective non-von Neumann languages has deprived computer designers of the motivation and the intellectual foundation needed to develop new computer architectures.[3]

Some examples of non-von Neumann languages are: APL, FP, FL, J, Lucid, NGL, ZPL, Mercury, and Plankalkül.[citation needed]

 

所以特寫

APL語言

概述

在許多應用場合下(數學、科學、工程技術、電腦設計、機器人、數據顯示、保險技術、傳統的數據處理等等)APL是一種非常有力的、表達豐富的和簡明的程式語言。它一般被用在一個與用戶接口的環境中。它最初的設計目的是將數學公式寫成一種電腦可以理解的方式。學它一般很容易,但要分析 APL 寫成的程序往往需要一段時間。與傳統的結構式程式語言不同的是,APL 的程序一般由一系列使用在序列上的單元的或雙元的函數或運算符號組成。由於APL擁有許多非標準的運算符號,這些符號之間沒有優先性(比如一般數學中的乘號、除號較加號、減號有優先權,APL中沒有這樣的優先權)。最初的APL語言沒有任何控制結構如循環(do-while)或者條件選擇(if-then-else),但一些序列運算符號可以用來模擬編程結構,比如iota(用來獲得一個從1至N的序列)可以用來模擬循環(for)。

APL 的工作環境被稱為工作場。在這個工作場內用戶可以定義程序和數據。數據也可以在工作場在程序外存在。用戶可以在程序外改變數據,比如:

\displaystyle N\leftarrow 4\ 5\ 6\ 7

將一個系列的數據4、5、6、7授予N。

\displaystyle N+4\,\!

輸出8、9、10、11。

\displaystyle +/N\,\!

輸出N內所有數的和,即22。

用戶可以將工作場連同其中的所有數據和程序儲存起來。在任何情況下,這些程序不是編譯執行,而是解釋執行的。

APL 最著名的就是它使用一組非ASCII符號。這些符號比一般常見的代數和計算符號要多。有人開玩笑說,用兩行這樣的奇形怪狀的符號就可以將所有航空控制的問題解決了。事實上,在一些APL版本中,用一行程序就可以將任何可計算的函數表達出來。在用一行你可以將這個函數的結構表達出來。由於它的精密的結構和非標準的符號,也有人將APL稱為「只寫語言」。除數學家外,其他人要讀APL寫的程序都感到非常困難。有些數學家覺得其它語言比APL難懂。由於APL使用不尋常的符號,許多編程員在寫APL程序時使用專門的APL鍵盤。今天也有不同的只使用ASCII字母寫APL的方法。

艾佛森後來還設計了一個APL的後續,稱為J語言,這個語言只使用ASCII符號。至今為止只有一種J語言。一些其它語言也提供類似APL的功能。A+是一種開源的程式語言,其許多指令與APL相同。

下面這個例子排列一個存在X里的詞的序列,排列標準是每個詞的長度:

X[X+.¬' ';]

下面是一個尋找所有1和R之間的質數的例子:

\displaystyle \left(\sim R\in R\circ .\times R\right)/R\leftarrow 1\downarrow \iota R

下面是這個程序的讀法(從右向左):

  1. \displaystyle \iota \,\! 建立含有從1到R的自然數的系列(假如程序開始時R=6,那麼 \displaystyle \iota R\,\! 是1 2 3 4 5 6)
  2. 放棄這個系列中的第一個元素(\displaystyle \downarrow)(\displaystyle 1\downarrow \iota R 是2 3 4 5 6)
  3. 令R成為這個系列(\displaystyle \leftarrow 是授值符號)
  4. 令R與R相乘而組成一個矩陣,實際上是組成一個R乘R的乘法表(\displaystyle \circ .\times
  5. 建立一個長度與R相同的系列,假如R中相應位置的數在乘法矩陣中出現,那麼在這個位置上的數就應該是1,否則0(\displaystyle \in),這個運算的結果是0 0 1 0 1
  6. 邏輯地否定的系列中的數,也就是說,1成為0,0成為1(\displaystyle \sim),結果是1 1 0 1 0
  7. 選擇R中相應的在新的系列中為1的數,這些數是質數(\displaystyle /\,\!),結果為2 3 5

 

只為『陣列運算』之『思維方法』故而已◎

為何不用 ROCK 64 耶?蓋無有,方才借樹莓派說也!

Repository

Debian/Raspbian

First you will need to set your Raspberry Pi up to connect to our public repository, This will allow you to keep your APL installation up to date with new releases.

The following are the supported Operating System codenames:

  • Raspbian (Debian)
    • wheezy (ARMHF) – Hardware Float: suitable for Dyalog 15.0 and earlier
    • jessie or later (ARMHF) – Hardware Float: this is required for Dyalog 16.0 and later

Please Note: We do not support ARMEL (Software Float) as we consider the performance of software float to be unacceptable on the Raspberry Pi.

wget -O - http://packages.dyalog.com/dyalog-apt-key.gpg.key | sudo apt-key add -
CODENAME=(lsb_release -sc) echo "deb http://packages.dyalog.com{CODENAME} main" | sudo tee /etc/apt/sources.list.d/dyalog.list

Please note: if you update the operating system on your Pi, then you should re-run these last two commands so that /etc/apt/sources.list.d/dyalog.list accurately reflects the codename of the version of the distribution that you are running.

【安裝】

sudo apt-get install dyalog-unicode

【測試】

pi@raspberrypi:~ $ dyalog
Dyalog APL/S Version 17.0.35961
Unicode Edition
Fri Apr 12 15:47:18 2019
/opt/mdyalog/17.0/32/unicode/Samples/fun/intro.dws saved Thu Mar 21 09:19:24 201
9

Rebuilding user command cache... done

                   Welcome to Dyalog APL.

    This message will only be displayed on your first run of Dyalog APL.
    If you would like to display this again run the following:

        )load intro

        *** Make sure you have saved any workspaces
            you have open before loading intro.     ***

                Try the following commands

    get_started     ⍝ useful commands to get you started
    APLKeys         ⍝ APL Keyboard Layout
    workspaces      ⍝ some example workspaces to try
    references      ⍝ list of useful websites

        To type APL Characters, hold down your windows key
                    while typing a character.

 

※ 參考︰

APL2 keyboard function to symbol mapping

Note the APL On/Off Key – topmost-rightmost key, just below. Also note the keyboard had some 55 unique (68 listed per tables above, including comparative symbols but several symbols appear in both monadic and dyadic tables) APL symbol keys (55 APL functions (operators) are listed in IBM’s 5110 APL Reference Manual), thus with the use of alt, shift and ctrl keys – it would theoretically have allowed a maximum of some 59 (keys) *4 (with 2-key pressing) *3 (with tri-key pressing, e.g., ctrl-alt-del) or some 472 different maximum key combinations, approaching the 512 EBCDIC character max (256 chars times 2 codes for each keys-combination). Again, in theory the keyboard pictured below would have allowed for about 472 different APL symbols/functions to be keyboard-input, actively used. In practice, early versions were only using something roughly equivalent to 55 APL special symbols (excluding letters, numbers, punctuation, etc. keys). Thus, early APL was then only using about 11% (55/472) of a symbolic language’s at-that-time utilization potential, based on keyboard # keys limits, again excluding numbers, letters, punctuation, etc. In another sense keyboard symbols utilization was closer to 100%, highly efficient, since EBCDIC only allowed 256 distinct chars, and ASCII only 128.

 

      N ← 4 5 6 7
      N + 4
8 9 10 11
      +/N
22
      R ← 6
      (~ R ∊ R ∘.× R)/R ← 1 ↓ ⍳ R
2 3 5

 

 

 

 

 

 

 

 

數字派 NumPy ︰陣列運算《四》

欲知所學固與不固,何妨來點測驗小猜謎

Quiz

A quiz is a form of game or mind sport, in which the players (as individuals or in teams) attempt to answer questions correctly. It is a game to test your knowledge about a certain subject. In some countries, a quiz is also a brief assessment used in education and similar fields to measure growth in knowledge, abilities, and/or skills.

Quizzes are usually scored in points and many quizzes are designed to determine a winner from a group of participants – usually the participant with the highest score. They may also involve eliminating those who get too many questions wrong, the winner being the last man standing.

Etymology

The earliest known examples of the word date back to 1780; its etymology is unknown, but it may have originated in student slang. It initially meant a “odd, eccentric person”[a] or a “joke, hoax”. Later (perhaps by association with words such as “inquisitive”) it came to mean “to observe, study intently”, and thence (from about mid-19th century) “test, exam.”[2][3]

There is a well-known myth about the word quiz that says that in 1791 a Dublin theater owner named Richard Daly made a bet that he could introduce a word into the language within 24 hours. He then went out and hired a group of street urchins to write the word “quiz”, which was a nonsense word, on walls around the city of Dublin. Within a day, the word was common currency and had acquired a meaning (since no one knew what it meant, everyone thought it was some sort of test) and Daly had some extra cash in his pocket.[4] However, there is no evidence to support the story, and the term was already in use before the alleged bet in 1791.

 

先讀『問題』 Question ︰

Are 1-dimensional numpy arrays equivalent to vectors? [closed]

I’m new to both linear algebra and numpy, so please bear with me. I’m taking a course on linear regression, where I learned that we can express our hypothesis as {\theta}^T X where \theta is our coefficient vector (written in math notation as a column vector) and X is our design matrix with m features and n rows.

Now, a vector can be viewed as one column or one row of a matrix. But in numpy, there is a difference between an array with shape (5,) and an array with shape (5,1).

  1. Is there a mathematical equivalent to the numpy distinction between shape (5,) and shape(5,1), or are we to view both as vectors?
  2. When we transpose a numpy array with shape (5,) its shape doesn’t change, whereas transposing an array with shape (5,1) results in the shape (1,5). What would be the correct numpy equivalent of {\theta}^T X?

 

嘗試自己『回答』 Answer …

然後認真『核實』 Verify ︰

 

 

 

 

可以虛心廣納『善解』也☆

1 Answer

 A NumPy array is a N-dimensional container of items of the same type and size. As a computer programming data structure, it is limited by resources and dtype — there are values which are not representable by NumPy arrays. Due to these limitations, NumPy arrays are not exactly equivalent to the mathematical concept of coordinate vectors. NumPy arrays are often used to (approximately) represent vectors however.Math also has a concept of vector spaces whose elements are called vectors. One example of a vector is an object with direction and magnitude. A coordinate vector is merely a represention of the vector with respect to a particular coordinate system. So while a NumPy array can at best record the coordinates of a vector (tacitly, with respect to a coordinate system), it can not capture the full abstract notion of a vector. The abstract notion of vector exists without any mention of coordinate system.

Moreover, vector spaces can be collections of things other than coordinates. For example, families of functions can form a vector space. The functions would then be vectors. So here is another example where NumPy arrays are not at all equivalent to vectors.


Linear algebra makes a distinction between “row vectors” and “column vectors”. There is no such distinction in NumPy. There are only n-dimensional arrays. Keep in mind that NumPy was built around a desire to generalize array-like containers to N dimensions where N is bigger than 2. So NumPy operations are defined in ways that generalize to higher dimensions.

For example, transposing a NumPy array of shape (a,b,c,d) returns an array of shape (d,c,b,a) — the axes are reversed. In two dimensions, this means an array of shape (a,b)(i.e. a rows, b columns) becomes an array of shape (b,a) (i.e, b rows, a columns). So NumPy’s notion of transposition matches up nicely with the linear algebra notion for 2-dimensional arrays.

But this also means that the transpose of a 1-dimensional NumPy array of shape (a,) still has shape (a,). Nothing changes. It is still the same 1-dimensional array. Thus there is no real distinction between “row vectors” and “column vectors”.

NumPy apes the concept of row and column vectors using 2-dimensional arrays. An array of shape (5,1) has 5 rows and 1 column. You can sort of think of this as a column vector, and wherever you would need a column vector in linear algebra, you could use an array of shape (n,1). Similarly, wherever you see a row vector in linear algebra you could use an array of shape(1,n).

However, NumPy also has a concept of broadcasting and one of the rules of broadcasting is that extra axes will be automatically added to any array on the left-hand side of its shape whenever an operation requires it. So, a 1-dimensional NumPy array of shape (5,) can broadcast to a 2-dimensional array of shape (1,5) (or 3-dimensional array of shape (1,1,5), etc).

This means a 1-dimensional array of shape (5,) can be thought of as a row vector since it will automatically broadcast up to an array of shape (1,5) whenever necessary.

On the other hand, broadcasting never adds extra axes on the right-hand side of the shape. You must do so explicitly. So if theta is an array of shape (5,), to create a “column vector” of shape (5,1) you must explicitly add the new axis yourself by using theta[:, np.newaxis] or the shorthand theta[:, None].

 

 

 

 

 

 

 

數字派 NumPy ︰陣列運算《三》

仔細閱讀清晰思考『普及函數』

Universal functions (ufunc)

A universal function (or ufunc for short) is a function that operates on ndarrays in an element-by-element fashion, supporting array broadcasting, type casting, and several other standard features. That is, a ufunc is a “vectorized” wrapper for a function that takes a fixed number of specific inputs and produces a fixed number of specific outputs.

In NumPy, universal functions are instances of the numpy.ufunc class. Many of the built-in functions are implemented in compiled C code. The basic ufuncs operate on scalars, but there is also a generalized kind for which the basic elements are sub-arrays (vectors, matrices, etc.), and broadcasting is done over other dimensions. One can also produce custom ufunc instances using the frompyfunc factory function.

Broadcasting

Each universal function takes array inputs and produces array outputs by performing the core function element-wise on the inputs (where an element is generally a scalar, but can be a vector or higher-order sub-array for generalized ufuncs). Standard broadcasting rules are applied so that inputs not sharing exactly the same shapes can still be usefully operated on. Broadcasting can be understood by four rules:

  1. All input arrays with ndim smaller than the input array of largest ndim, have 1’s prepended to their shapes.
  2. The size in each dimension of the output shape is the maximum of all the input sizes in that dimension.
  3. An input can be used in the calculation if its size in a particular dimension either matches the output size in that dimension, or has value exactly 1.
  4. If an input has a dimension size of 1 in its shape, the first data entry in that dimension will be used for all calculations along that dimension. In other words, the stepping machinery of the ufunc will simply not step along that dimension (the stride will be 0 for that dimension).

Broadcasting is used throughout NumPy to decide how to handle disparately shaped arrays; for example, all arithmetic operations (+,-, *, …) between ndarrays broadcast the arrays before operation.

A set of arrays is called “broadcastable” to the same shape if the above rules produce a valid result, i.e., one of the following is true:

  1. The arrays all have exactly the same shape.
  2. The arrays all have the same number of dimensions and the length of each dimensions is either a common length or 1.
  3. The arrays that have too few dimensions can have their shapes prepended with a dimension of length 1 to satisfy property 2.

Example

If a.shape is (5,1), b.shape is (1,6), c.shape is (6,) and d.shape is () so that d is a scalar, then a, b, c, and d are all broadcastable to dimension (5,6); and

  • a acts like a (5,6) array where a[:,0] is broadcast to the other columns,
  • b acts like a (5,6) array where b[0,:] is broadcast to the other rows,
  • c acts like a (1,6) array and therefore like a (5,6) array where c[:] is broadcast to every row, and finally,
  • d acts like a (5,6) array where the single value is repeated.

………

 

文本內容,然後藉著

numpy.vectorize

class numpy.vectorize(pyfunc, otypes=None, doc=None, excluded=None, cache=False, signature=None)
 

Generalized function class.

Define a vectorized function which takes a nested sequence of objects or numpy arrays as inputs and returns a single numpy array or a tuple of numpy arrays. The vectorized function evaluates pyfunc over successive tuples of the input arrays like the python map function, except it uses the broadcasting rules of numpy.

The data type of the output of vectorized is determined by calling the function with the first element of the input. This can be avoided by specifying the otypes argument.

Parameters:
pyfunc : callable

A python function or method.

otypes : str or list of dtypes, optional

The output data type. It must be specified as either a string of typecode characters or a list of data type specifiers. There should be one data type specifier for each output.

doc : str, optional

The docstring for the function. If None, the docstring will be the pyfunc.__doc__.

excluded : set, optional

Set of strings or integers representing the positional or keyword arguments for which the function will not be vectorized. These will be passed directly to pyfunc unmodified.

New in version 1.7.0.

cache : bool, optional

If True, then cache the first function call that determines the number of outputs if otypes is not provided.

New in version 1.7.0.

signature : string, optional

Generalized universal function signature, e.g., (m,n),(n)->(m) for vectorized matrix-vector multiplication. If provided, pyfunc will be called with (and expected to return) arrays with shapes given by the size of corresponding core dimensions. By default, pyfunc is assumed to take scalars as input and output.

New in version 1.12.0.

Returns:
vectorized : callable

Vectorized function.

See also

frompyfunc
Takes an arbitrary Python function and returns a ufunc

Notes

The vectorize function is provided primarily for convenience, not for performance. The implementation is essentially a for loop.

If otypes is not specified, then a call to the function with the first argument will be used to determine the number of outputs. The results of this call will be cached if cache is True to prevent calling the function twice. However, to implement the cache, the original function must be wrapped which will slow down subsequent calls, so only do this if your function is expensive.

The new keyword argument interface and excluded argument support further degrades performance.

References

[1] NumPy Reference, section Generalized Universal Function API.

 

玩味理蘊深化了解『向量化』,自可知

Nicolas P. Rougier 《From Python to Numpy》一書

第二章論旨也。

Introduction

Simple example

Note

You can execute any code below from the code folder using the regular python shell or from inside an IPython session or Jupyter notebook. In such a case, you might want to use the magic command %timeit instead of thecustom one I wrote.

Numpy is all about vectorization. If you are familiar with Python, this is the main difficulty you’ll face because you’ll need to change your way of thinking and your new friends (among others) are named “vectors”, “arrays”, “views” or “ufuncs”.

………

 

 

 

 

 

 

 

數字派 NumPy ︰陣列運算‧《外傳一》求根

1280px-Supremum_illustration

最小上界性質

Let S be a non-empty set of real numbers:
A real number x is called an upper bound for S if x ≥ s for all s ∈ S. A real number x is the least upper bound (or supremum) for S if x is an upper bound for S and x ≤ y for every upper bound y of S.

從『疊套區間』的觀點來看,一個『超實數r^{*} = r + \delta x 就可以表達成 [r - \delta \epsilon, r + \delta \epsilon],而且說 st \left( [r - \delta \epsilon, r + \delta \epsilon] \right) = \{r\},由於它只有『唯一的』一個元素,所以被稱作『單子集合』 singleton set。假使我們思考一個『單調上升有上界a_n, a_{n+1} > a_n, a_n < U, n=1 \cdots n 的『序列』,會發現它一定有『最小上界』。假設 H 是一個『巨量』,那麼 st \left( \bigcap \limits_{1}^{\infty} [a_n, 2 a_H -a_n] = a_{\infty} \right)

。這就是『實數』的『基本性質』,任何一有極限的『序列』收斂於一個『唯一』的『實數』,一般稱之為『實數』的『完備性』 completeness,由於我們是站在『超實數』的立場,選擇了『疊套區間』的觀點,加之以『無窮小』量不滿足『實數』的『阿基米德性質』,所以這個『實數』的『完備性』只是從『疊套區間』確定了一個『單子集合』 推導的結論。對比著來看,這一個『有理數』序列 x_0 = 1, x_{n+1} = \frac{x_n + \frac{2}{x_n}}{2} 的『極限x_{\infty} = \sqrt{2} ,它可從求解 x_H = \frac{x_H + \frac{2}{x_H}}{2} 得到,然而它並不是『有理數』,所以說『有理數』不具有『完備性』 。那麼對一個『非空有上界』的『集合S,也可以用『二分逼近法』論證如下︰

由於 S 有上界,就說是 b_1 吧,因為 S 不是空集合,一定有一個元素 a_1 不是它的上界。這兩個序列可以遞迴的如此定義,計算 \frac{a_n + b_n}{2},如果它是 S 的上界,那麼 a_{n+1} = a_n, \ b_{n+1} = \frac{a_n + b_n}{2},否則 S 中必有一個元素 s,而且 s > \frac{a_n + b_n}{2},此時選擇 a_{n+1} = s, \ b_{n+1} = b_n,如此 a_1 \leq a_2 \leq a_3 \leq \cdots \leq b_3 \leq b_2 \leq b_1 而且 a_H - b_H \approx 0,所以一定存在一個 L = a_{\infty} = b_{\infty},此為 S 之最小上界。

同理 S 的補集 R - S 就會有『下界』,而且會有『最大下界』。因此我們將一個有『上界』與『下界』的集合,簡稱之為『有界集合』。

─── 《【SONIC Π】電路學之補充《四》無窮小算術‧下

 

實數的『完備性』邏輯上蘊涵了『介值定理』︰

若問一個人從山腳走到山頂,是否他經過了此山的所有高度?可能有人會說題意模糊難於論斷。也可能有人依據常理常義衡量講當然如此。想那山道蜒是『連續』的,人腳步伐落處卻是『離散』的 ,固然『連續』包含著『離散』!!然而『離散』能近似『連續』耶??所謂天衣無縫,實數方才完備乎!!

Completeness of the real numbers

Intuitively, completeness implies that there are not any “gaps” (in Dedekind’s terminology) or “missing points” in the real number line. This contrasts with the rational numbers, whose corresponding number line has a “gap” at each irrational value. In the decimal number system, completeness is equivalent to the statement that any infinite string of decimal digits is actually a decimal representation for some real number.

Depending on the construction of the real numbers used, completeness may take the form of an axiom (the completeness axiom), or may be a theorem proven from the construction. There are many equivalent forms of completeness, the most prominent being Dedekind completeness and Cauchy completeness (completeness as a metric space).

 

因其完備,對『連續函數』而言,介值定理不得不然嗎!!??

Intermediate value theorem

In mathematical analysis, the intermediate value theorem states that if a continuous function, f, with an interval, [a, b], as its domain, takes values f(a) and f(b) at each end of the interval, then it also takes any value between f(a) and f(b) at some point within the interval.

This has two important corollaries: 1) If a continuous function has values of opposite sign inside an interval, then it has a root in that interval (Bolzano’s theorem).[1] 2) The image of a continuous function over an interval is itself an interval.

Intermediate value theorem: Let f be a defined continuous function on [a, b] and let s be a number with f(a) < s < f(b). Then there exists at least one x with f(x) = s

─── 摘自《時間序列︰生成函數‧漸近展開︰無限大等級 V

 

然於如何『求根』乙事?卻是三緘其口哩!更別說當一個『多項式方程式』的『次方數』超過了『四階』就沒有『一般解』!!只得用數值方法耶??

求根演算法

數學電腦運算中,對於一個已知的從實數集合對映到實數集合,或者從複數集合對映到複數集合連續函數 \displaystyle f(x) ,搜尋變數 \displaystyle x 使得 \displaystyle f(x)=0 (此時,變數 \displaystyle x x稱為 \displaystyle f(x)=0 的根、 \displaystyle f(x) 的零點)的演算法,稱為求根演算法。在許多情況下,函數的零點無法被準確計算出,也無法被解析解表示;是故,求根演算法在實數集合下只提供一個以浮點數表示的近似解,或者一個足夠小的解的存在區間,在複數集合下只提供一個複根的圓盤(輸出一個區間或一個圓盤等價於輸出一個根的近似值及其誤差上限)。

解方程式 \displaystyle f(x)=g(x) 與求 \displaystyle f(x)-g(x) 的根是等價的。因此求根演算法可以求解任何以連續函數定義的方程式。然而,許多情況下,求根演算法只能找到方程式的某些根,而不能保證所有根都能找到;特別指出,演算法未找到根,並不代表方程式確實無根。

大多數的數值求根演算法都使用疊代法,生成一個以方程式的根為極限的收斂數列。它們需要一個或多個根作為疊代的初期值,嗣後每次疊代都生成一個逐步逼近根的值。由於疊代法必須在有限步內終止於某個點,這些方法都只能提供一個根的近似值,而不能提供一個精確解。 許多方法是通過代入上一個疊代值來計算一個輔助方程式,從而得出下一個疊代值的。此處所指的輔助方程式是指為了使源方程式的根是一個定點並使疊代值能更快地收斂到這些定點而設計的一個方程式,因此疊代值的極限是這個輔助方程式的一個定點。

求根演算法的效能是數值分析的研究範疇。一種演算法的效率可能大幅度取決於已知點的性質。例如,一部分演算法都使用輸入函數的導數(此要求函數不但連續,而且可導),而其他演算法則能用於任何一個連續函數。在一般情況下,數值演算法不能保證找到一個函數的所有根,因此演算法未能找到根並不能證明方程式無根。然而,對於多項式,存在特定的使用代數學性質以定位根的所在區間(或複根所在的圓盤)的演算法,這個區間(或圓盤)足夠小以能保證數值演算法(例如牛頓法)能收斂到唯一被定位的根。

 

考察其術︰

包圍法

包圍法是指通過疊代確定根的所在區間,並逐漸縮小其區間長度的演算法。當區間變得足夠小時,則認為根已經被找到。一般地,包圍法以介值定理為基礎,且能夠求出根的絕對誤差上限;而當函數是一個多項式時,還有其它基於施圖姆定理笛卡兒符號法則的方法,能夠在一個區間內求出精確的根。

二分法

最簡單的求根演算法為二分法︰令 \displaystyle f(x) 為一個連續函數,且已知存在區間 \displaystyle [a,b] 滿足 \displaystyle f(a) 符號互異。令 \displaystyle c=(a+b)/2 區間的中點),則 \displaystyle f(a) 和 \displaystyle f(c)\displaystyle f(c) 和 \displaystyle f(b) 中,必恰有一者符號互異,並將已知根所在區間的長度縮短為一半。對被縮短的區間重複上述步驟,直到找到根。

縱二分法具有強健性,但其只能求得區間內的一個且只有一位精度的解。此外在合適的條件下,亦存在其他能更快求得精確解的方法。

盈不足術法

盈不足術法與二分法相似。異處在於,盈不足術以方式計算出疊代點,

\displaystyle c={\frac {af(b)-bf(a)}{f(b)-f(a)}}.
盈不足術法也類似於割線法。異處在於,盈不足術法不保留前兩次疊代點,而是在根的兩側各保留一點。 盈不足術法能以較二分法更快的速度求根,且不會如割線法一樣發散(不收斂);但在一些簡單實現的情形中可能因為捨入誤差而無法收斂。[需要解釋]

Ridders法是盈不足術法的一個變形。其使用區間中點的函數值,構造出一個具有相同零點的函數,再用盈不足術法求解之。這個方法維持了一定的強健性外,亦使演算法更快收斂。

插值法

許多求根演算法通過插值來實現。即,使用上一步計算出的根的多個近似值,藉助一個以插值法求出的低次多項式,以逼近一個函數。然後計算多項式的根,並用其作新的函數的根的近似值,重複此流程。

兩個函數值可利用插值法求得一個一次多項式,即以一條直線逼近一個函數圖像。此乃割線法盈不足術法的基礎。進而,三個函數值可求得一個二次函數,即以一條拋物線逼近一個函數圖像。此即Muller法

疊代法

雖然所有求根演算法都通過疊代,但一個疊代的求根演算法,通常使用一種特定的疊代類型,包括定義一個輔助函數,應用上一步計算出的根的近似值,求得新的近似值。輔助函數到逹一個定點(到逹所需的精度),即新疊代的近似值充分接近上一個疊代值時,疊代停止。

牛頓法(及類似的以導數為基礎的方法)

牛頓法假定函數 \displaystyle f 的導數連續的。如果起始點距離根太遠,牛頓法可能不收斂。然而,其若收斂,速度將較二分法快,且通常為二次收斂。牛頓法也是一種重要的演算法,因為它能容易地推廣到高維問題。類似牛頓法且有更高次的收斂性的演算法為Householder法。具有三次收斂性的Householder法是Halley法

割線法

將牛頓法中的導數替換為一個差分式,即得到割線法。 這種方法的優點在於不需要計算導數,但其代價是收斂速度較慢(收斂次數約為1.6)。把割線法推廣到高維的演算法是Broyden法

逆插值法

對函數 \displaystyle f 進行逆插值,能夠避免插值法中出現複數。這種方法稱為逆二次插值法。其收斂速度漸近快於割線法;但當疊代離根較遠時,逆二次插值法往往表現不佳。

 

初始揣測『根之所在』,選址定基難有善法也★

比方講︰

『二分法』之所以強健,雖得『介值定理』之本,尚須先找到函數『變號區間』也;『牛頓法』

Newton’s method

In numerical analysis, Newton’s method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function. It is one example of a root-finding algorithm.

The Newton–Raphson method in one variable is implemented as follows:

The method starts with a function f defined over the real numbers x, the function’s derivative f ′, and an initial guess x0 for a root of the function f. If the function satisfies the assumptions made in the derivation of the formula and the initial guess is close, then a better approximation x1 is

\displaystyle x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}\,.

Geometrically, (x1, 0) is the intersection of the x-axis and the tangent of the graph of f at (x0, f (x0)).

The process is repeated as

\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\,

until a sufficiently accurate value is reached.

 

縱使快速,有『解析幾何』的直覺,第一步踏錯怕會無『回頭路』矣。

猶恐讀者誤解所指,特以『單峰映象』例釋一下︰

一九七六年,澳洲科學家 Robert McCredie May 發表了一篇《Simple mathematical models with very complicated dynamics》文章,提出了一個『單峰映象』 logistic map 遞迴關係式 x_{n+1} = r x_n(1 - x_n), \ 0\leq x_n <1。這個遞迴關係式很像是『差分版』的『 logistic equation』,竟然是產生『混沌現象』的經典範例。假使說一個『遞迴關係式』有『極限值x_{\infty} = x_H 的話,此時 x_H = r x_H(1-x_H),可以得到 r{x_H}^2 = (r - 1) x_H,於是 x_H \approx 0 或者 x_H \approx \frac{r - 1}{r}。在 r < 1 之時,『單峰映象』或快或慢的收斂到『』;當 1 < r < 2 之時,它很快的逼近 \frac{r - 1}{r};於 2 < r < 3 之時,線性的上下震盪趨近 \frac{r - 1}{r};雖然 r=3 也收斂到 \frac{r - 1}{r},然而已經是很緩慢而且不是線性的了;當 r > 1 + \sqrt{6} \approx 3.45 時,對幾乎各個『初始條件』而言,系統開始發生兩值『震盪現象』,而後變成四值、八值、十六值…等等的『持續震盪』;最終於大約 r = 3.5699 時,這個震盪現象消失了,系統就步入了所謂的『混沌狀態』的了!!

Maple_logistic_plot_small

………

回想之前『λ 運算』裡的『遞迴函式』,與數學中的『定點』定義,『單峰映象』可以看成函數 f(x) = r \cdot x(1 - x) 的『迭代求值』︰x_1 = f(x_0), x_2 = f(x_1), \cdots x_{k+1} = f(x_k) \cdots。當 f^{(p)} (x_f) = f \cdots (p -2) \times f \cdots f(x_f) = x_f,這個 x_f 就是『定點』,下圖中顯示出不同的 r 值的求解現象,從有『定點』向『震盪』到『混沌』。

LogisticCobwebChaos

─── 參讀《【SONIC Π】電路學之補充《四》無窮小算術‧中下上

 

『陣列運算』可以立馬就放縮『疊套區間』利乎行ㄚ◎

 

 

 

 

 

 

 

 

數字派 NumPy ︰陣列運算《二》

將如何理解 NumPy 的 ndarray 呢?簡短概略之 Quickstart tutorial 恐不足也︰

The Basics

NumPy’s main object is the homogeneous multidimensional array. It is a table of elements (usually numbers), all of the same type, indexed by a tuple of positive integers. In NumPy dimensions are called axes.

For example, the coordinates of a point in 3D space [1, 2, 1] has one axis. That axis has 3 elements in it, so we say it has a length of 3. In the example pictured below, the array has 2 axes. The first axis has a length of 2, the second axis has a length of 3.

[[ 1., 0., 0.],
 [ 0., 1., 2.]]

NumPy’s array class is called ndarray. It is also known by the alias array. Note that numpy.array is not the same as the Standard Python Library class array.array, which only handles one-dimensional arrays and offers less functionality. The more important attributes of anndarray object are:

ndarray.ndim
the number of axes (dimensions) of the array.
ndarray.shape
the dimensions of the array. This is a tuple of integers indicating the size of the array in each dimension. For a matrix with n rows and m columns, shape will be (n,m). The length of the shape tuple is therefore the number of axes, ndim.
ndarray.size
the total number of elements of the array. This is equal to the product of the elements of shape.
ndarray.dtype
an object describing the type of the elements in the array. One can create or specify dtype’s using standard Python types. Additionally NumPy provides types of its own. numpy.int32, numpy.int16, and numpy.float64 are some examples.
ndarray.itemsize
the size in bytes of each element of the array. For example, an array of elements of type float64 has itemsize 8 (=64/8), while one of type complex32 has itemsize 4 (=32/8). It is equivalent to ndarray.dtype.itemsize.
ndarray.data
the buffer containing the actual elements of the array. Normally, we won’t need to use this attribute because we will access the elements in an array using indexing facilities.

 

蓋需要深入認識陣列這個資料結構呦!

Array data structure

In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.[1][2][3] The simplest type of data structure is a linear array, also called one-dimensional array.

For example, an array of 10 32-bit integer variables, with indices 0 through 9, may be stored as 10 words at memory addresses 2000, 2004, 2008, … 2036, so that the element with index i has the address 2000 + 4 × i.[4]

The memory address of the first element of an array is called first address or foundation address.

Because the mathematical concept of a matrix can be represented as a two-dimensional grid, two-dimensional arrays are also sometimes called matrices. In some cases the term “vector” is used in computing to refer to an array, although tuples rather than vectors are the more mathematically correct equivalent. Tables are often implemented in the form of arrays, especially lookup tables; the word table is sometimes used as a synonym of array.

Arrays are among the oldest and most important data structures, and are used by almost every program. They are also used to implement many other data structures, such as lists and strings. They effectively exploit the addressing logic of computers. In most modern computers and many external storage devices, the memory is a one-dimensional array of words, whose indices are their addresses. Processors, especially vector processors, are often optimized for array operations.

Arrays are useful mostly because the element indices can be computed at run time. Among other things, this feature allows a single iterative statement to process arbitrarily many elements of an array. For that reason, the elements of an array data structure are required to have the same size and should use the same data representation. The set of valid index tuples and the addresses of the elements (and hence the element addressing formula) are usually,[3][5] but not always,[2] fixed while the array is in use.

The term array is often used to mean array data type, a kind of data type provided by most high-level programming languages that consists of a collection of values or variables that can be selected by one or more indices computed at run-time. Array types are often implemented by array structures; however, in some languages they may be implemented by hash tables, linked lists, search trees, or other data structures.

The term is also used, especially in the description of algorithms, to mean associative array or “abstract array”, a theoretical computer science model (an abstract data type or ADT) intended to capture the essential properties of arrays.

History

The first digital computers used machine-language programming to set up and access array structures for data tables, vector and matrix computations, and for many other purposes. John von Neumann wrote the first array-sorting program (merge sort) in 1945, during the building of the first stored-program computer.[6]p. 159 Array indexing was originally done by self-modifying code, and later using index registers and indirect addressing. Some mainframes designed in the 1960s, such as the Burroughs B5000 and its successors, used memory segmentation to perform index-bounds checking in hardware.[7]

Assembly languages generally have no special support for arrays, other than what the machine itself provides. The earliest high-level programming languages, including FORTRAN (1957), Lisp (1958), COBOL (1960), and ALGOL 60 (1960), had support for multi-dimensional arrays, and so has C (1972). In C++ (1983), class templates exist for multi-dimensional arrays whose dimension is fixed at runtime[3][5] as well as for runtime-flexible arrays.[2]

 

若說小小範例

An example

 

裡的 reshape 費思量?

numpy.reshape

numpy.reshape(a, newshape, order=’C’)
Gives a new shape to an array without changing its data.

Parameters:
a : array_like

Array to be reshaped.

newshape : int or tuple of ints

The new shape should be compatible with the original shape. If an integer, then the result will be a 1-D array of that length. One shape dimension can be -1. In this case, the value is inferred from the length of the array and remaining dimensions.

order : {‘C’, ‘F’, ‘A’}, optional

Read the elements of a using this index order, and place the elements into the reshaped array using this index order. ‘C’ means to read / write the elements using C-like index order, with the last axis index changing fastest, back to the first axis index changing slowest. ‘F’ means to read / write the elements using Fortran-like index order, with the first index changing fastest, and the last index changing slowest. Note that the ‘C’ and ‘F’ options take no account of the memory layout of the underlying array, and only refer to the order of indexing. ‘A’ means to read / write the elements in Fortran-like index order if a is Fortrancontiguous in memory, C-like order otherwise.

Returns:
reshaped_array : ndarray

This will be a new view object if possible; otherwise, it will be a copy. Note there is no guarantee of thememory layout (C- or Fortran- contiguous) of the returned array.

See also

ndarray.reshape
Equivalent method.

 

怕不知

Element identifier and addressing formulas

When data objects are stored in an array, individual objects are selected by an index that is usually a non-negative scalar integer. Indexes are also called subscripts. An index maps the array value to a stored object.

There are three ways in which the elements of an array can be indexed:

  • 0 (zero-based indexing): The first element of the array is indexed by subscript of 0.[8]
  • 1 (one-based indexing): The first element of the array is indexed by subscript of 1.
  • n (n-based indexing): The base index of an array can be freely chosen. Usually programming languages allowing n-based indexing also allow negative index values and other scalar data types like enumerations, or characters may be used as an array index.

Using zero based indexing is design choice of many influential programming languages, including C, Java and Lisp. This leads to simpler implementation where the subscript refers to an offset from the starting position of an array, so the first element has an offset of zero.

Arrays can have multiple dimensions, thus it is not uncommon to access an array using multiple indices. For example, a two-dimensional array A with three rows and four columns might provide access to the element at the 2nd row and 4th column by the expressionA[1][3] in the case of a zero-based indexing system. Thus two indices are used for a two-dimensional array, three for a three-dimensional array, and n for an n-dimensional array.

The number of indices needed to specify an element is called the dimension, dimensionality, or rank of the array.

In standard arrays, each index is restricted to a certain range of consecutive integers (or consecutive values of some enumerated type), and the address of an element is computed by a “linear” formula on the indices.

One-dimensional arrays

A one-dimensional array (or single dimension array) is a type of linear array. Accessing its elements involves a single subscript which can either represent a row or column index.

As an example consider the C declaration int anArrayName[10];

Syntax : datatype anArrayname[sizeofArray];

In the given example the array can contain 10 elements of any value available to the int type. In C, the array element indices are 0-9 inclusive in this case. For example, the expressions anArrayName[0] and anArrayName[9] are the first and last elements respectively.

For a vector with linear addressing, the element with index i is located at the address B + c × i, where B is a fixed base address and c a fixed constant, sometimes called the address increment or stride.

If the valid element indices begin at 0, the constant B is simply the address of the first element of the array. For this reason, the C programming language specifies that array indices always begin at 0; and many programmers will call that element “zeroth” rather than “first”.

However, one can choose the index of the first element by an appropriate choice of the base address B. For example, if the array has five elements, indexed 1 through 5, and the base address B is replaced by B + 30c, then the indices of those same elements will be 31 to 35. If the numbering does not start at 0, the constant B may not be the address of any element.

Multidimensional arrays

For a multidimensional array, the element with indices i,j would have address B + c · i + d · j, where the coefficients c and d are the row and column address increments, respectively.

More generally, in a k-dimensional array, the address of an element with indices i1, i2, …, ik is

B + c1 · i1 + c2 · i2 + … + ck · ik.

For example: int a[2][3];

This means that array a has 2 rows and 3 columns, and the array is of integer type. Here we can store 6 elements they will be stored linearly but starting from first row linear then continuing with second row. The above array will be stored as a11, a12, a13, a21, a22, a23.

This formula requires only k multiplications and k additions, for any array that can fit in memory. Moreover, if any coefficient is a fixed power of 2, the multiplication can be replaced by bit shifting.

The coefficients ck must be chosen so that every valid index tuple maps to the address of a distinct element.

If the minimum legal value for every index is 0, then B is the address of the element whose indices are all zero. As in the one-dimensional case, the element indices may be changed by changing the base address B. Thus, if a two-dimensional array has rows and columns indexed from 1 to 10 and 1 to 20, respectively, then replacing B by B + c1 – − 3 c1 will cause them to be renumbered from 0 through 9 and 4 through 23, respectively. Taking advantage of this feature, some languages (like FORTRAN 77) specify that array indices begin at 1, as in mathematical tradition while other languages (like Fortran 90, Pascal and Algol) let the user choose the minimum value for each index.

………

Compact layouts

Often the coefficients are chosen so that the elements occupy a contiguous area of memory. However, that is not necessary. Even if arrays are always created with contiguous elements, some array slicing operations may create non-contiguous sub-arrays from them.

Illustration of row- and column-major order

There are two systematic compact layouts for a two-dimensional array. For example, consider the matrix

\displaystyle \mathbf {A} ={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.

In the row-major order layout (adopted by C for statically declared arrays), the elements in each row are stored in consecutive positions and all of the elements of a row have a lower address than any of the elements of a consecutive row:
1 2 3 4 5 6 7 8 9

In column-major order (traditionally used by Fortran), the elements in each column are consecutive in memory and all of the elements of a column have a lower address than any of the elements of a consecutive column:

1 4 7 2 5 8 3 6 9

For arrays with three or more indices, “row major order” puts in consecutive positions any two elements whose index tuples differ only by one in the last index. “Column major order” is analogous with respect to the first index.

In systems which use processor cache or virtual memory, scanning an array is much faster if successive elements are stored in consecutive positions in memory, rather than sparsely scattered. Many algorithms that use multidimensional arrays will scan them in a predictable order. A programmer (or a sophisticated compiler) may use this information to choose between row- or column-major layout for each array. For example, when computing the product A·B of two matrices, it would be best to have A stored in row-major order, and B in column-major order.

 

生疑惑哩☂

 

而後才好了陣列運算之基本矣☆

Basic Operations

Arithmetic operators on arrays apply elementwise. A new array is created and filled with the result.

 

Unlike in many matrix languages, the product operator * operates elementwise in NumPy arrays. The matrix product can be performed using the @ operator (in python >=3.5) or the dot function or method: