Theme 11. Approximation. Linear and quadratic approximations. Spline approximation

1. Approximation

The disadvantage of interpolation is that for many nodes a polynomial of high degree is formed. If the original data were not obtained accurately, then the interpolating function though accurately passes through nodal points, nevertheless is inaccurate. In such cases, an approximation should be used - the definition of the function that closest (best) approaches the nodal points.

Approximation - finding a function of a given type, which at points,,, .. took values ​​as close as possible to the values,,, ..,.

Types of approximating functions:

Types of approximating functions:

• y = ax + b;
• y = ax ^ 2 + bx + c;
• y = ax ^ m;
• y = a ln (x) + b;
• y = x / (ax + b) and others.

Smallest squares method

For a function given by a table of values ​​(approximation nodes), find a function of a predetermined form, for example, the polynomial is degree so that the sum of the squares of deviations from the nodal points was the smallest. In other words, find the coefficients of this polynomial from the condition that the line should as close as possible pass near the nodes of approximation.

Linear approximation

The essence of the method. Straight line P ₂ (x) = a ₀ + a ₁ x be best to approach all these points (x _o ; y _o ), (x ₁ ; y ₁ ), (x ₂ ; y ₂ ) and (x ₃ ; y ₃ ).

Quadratic approximation

Output data:

• given the function f (x) at points and more points: f (x _o ) = y _o ; f (x ₁ ) = y ₁ ; f (x ₂ ) = y ₂ ; and f (x ₃ ) = y ₃ ;
• the order of the sought approximating polynomial n = 2.

The essence of the method. Figure quadratic function P ₂ (x) = a ₀ + a ₁ x + a ₂ x ² should be the best to approach all these points (x _o ; y _o ), (x ₁ ; y ₁ ), (x ₂ ; y ₂ ) and (x ₃ ; y ₃ ).

2. Spline approximation

Spline approximation reduces to the construction of segments of curves of low orders (usually of the 3rd order), which approximate the given nodes and bind to each other in the first or second order of smoothness.

A split is called a function that, along with several derivatives, is continuous on the segment [a, b], and on each private interval of this segment [xi, xi + 1] separately are some polynomials of low degree.

Spline interpolation resembles a Lagrangian that requires only values ​​in nodes, but not its derivatives.

3. Curves Bezier

Bezier curves are widely used in computer graphics to simulate smooth lines. The curve is entirely in the convex hull of its reference points. This feature of Bezier curves allows you to intuitively control the curve parameters in a graphical interface using its reference points. In addition, the affine curve transformation (transfer, scaling, rotation, etc.) can also be accomplished by applying appropriate transformations to the reference points.

Of greatest importance are Bezier curves of the second and third degrees (quadratic and cubic). For the construction of complex lines of form, separate Bezier curves can be sequentially connected to each other in the split Bezier. In order to ensure the smoothness of the line at the junction of the two curves, three adjacent reference points of both curves should lie in one straight line.

In vector graphics programs like Adobe Illustrator or Inkscape such pieces known as "Way» ( path ). In modern graphic systems and formats, such as PostScript (as well as Adobe Illustrator and Portable Document Format ( PDF ) formats based on it ), Scalable Vector Graphics ( SVG ), Metafont , CorelDraw, and GIMP for representing curvilinear shapes are used. Bezier splines are composed of cubic curves

Linear curves

When n = 1, the curve represents a segment of a straight line, the reference points P0 and P1 determine its beginning and end. The curve is given by the equation:

The parameter t in the function that describes the linear case of the Bezier curve determines where exactly at a distance from P0 to P1 is B (t). For example, at t = 0,25 the value of the function B (t) corresponds to a quarter of the distance between the points P0 and P1. The parameter t varies from 0 to 1, and B (t) describes the line segment between the points P0 and P1.

Quadratic curves

The Bezier quadratic curve (n = 2) is given by three reference points: P0, P1 and P2.

Quadratic Bezier curves in splines are used to describe character form in TrueType fonts and in SWF files.

To construct the Bezier quadratic curves, it is necessary to select two intermediate points Q0 and Q1 from the condition that the parameter t varies from 0 to 1:

The point Q0 varies from P0 to P1 and describes the Bezier curve.

The point Q1 varies from P1 to P2 and also describes the Bezier curve.

Point B varies from Q0 to Q1 and describes the Bezier curve.

Cubic curves

In the parametric form, the Bezier cubic curve (n = 3) is described by the equation:

Four reference points P0, P1, P2 and P3 given in the 2- or 3-dimensional space determine the shape of the curve. Line takes origin from P0 pointing to P1 and ends at P3 pointing to it from P2. That is, the curve does not pass through points P1 and P2, they are used to indicate its direction. The length of the segment between P0 and P1 determines how soon the curve returns to P3.

In the matrix form, the Bezier cubic curve is written as follows:

where

where it is called the base Bezier matrix.

To construct higher-order curves, more intermediate points are needed. For a cubic curve, these are intermediate points Q0, Q1 and Q2 describing linear curves, as well as points R0 and R1 that describe quadratic curves.

Properties of the Bezier curve

• Continuity of filling segment between initial and final points;
• the curve always lies inside the figure formed by the lines connecting the control points;
• in the presence of only two control points, the segment represents a straight line;
• Bezier curve is symmetric, that is, the exchange of places between the initial and the endpoints (changing the direction of the trajectory) does not affect the shape of the curve;
• Zooming and changing the proportions of the Bezier curve does not violate its stability, since it is "affinously invariant" from a mathematical point of view;
• changing the coordinates of at least one of the points leads to a change in the shape of the entire Bezier curve;
• the degree of the curve is always one step lower than the number of control points, for example, at three control points the shape of the curve - a parabola;
• the circle can not be described by the parametric equation of the Bezier curve;
• it is impossible to create parallel Bezier curves, except in trivial cases.

4. Processing data in Excel

Excel is a spreadsheet processor for creating spreadsheets and processing tabular data.

A spreadsheet is a matrix divided by rows and columns, at the intersection of which cells with unique names are formed. Cells are the main element of a table in which data can be input and can be referenced by cell names. Data includes: numbers , dates, time of day, text or symbolic data and formulas.

Data processing includes:

• conducting computations using formulas and functions embedded in the editor;
• construction of diagrams;
• data processing in lists (Sorting, AutoFilter, Advanced Filter, Form, Summary, Summary Table);
• solution of optimization problems (Parameter selection, Search solution, Scripts "what - if other tasks);
• statistical data processing, analysis and forecasting (analysis tools from the add-in "Analysis package").

Excel is not only a means of automating calculations, but also a means of simulating different situations.

Scope of Excel: Planned-Financial and Accounting Estimates, Decision Support Systems (DSS) and other areas of application.

Create a new workbook

                        When you start Excel, the application window displays a new working book, Book 1.

The window has five main areas:

• menu bar;
• toolbar;
• state line;
• line of input;
• worksheet window area.

Basic data processing is carried out using commands from the menu bar. The Standard and Format Toolbars are embedded in the Excel panels, which are arranged below the menu bar and contain certain sets of icons (buttons). The bulk of the icons are designed to execute the most frequently used commands from the menu bar.

A formula line is used to enter and edit values ​​or formulas in cells or charts. The name field is the window to the left of the line of formulas, which displays the name of the active cell. Icons: X, V, fx, located to the left of the line of formulas, are the buttons for canceling, inserting and inserting functions respectively.

The status bar is located at the bottom of the screen. The left side of the status bar indicates the status of the workspace of the spreadsheet (Finish, Input, Edit, Specify). In addition, the left side of the line will briefly describe the results of the executed team. The results of the calculations are displayed on the right side of the status line (when performing automatic calculations using the context menu of the status bar) and the Ins, Caps Lock, Num Lock, Scroll Lock keys are displayed.

The workbook (Excel document) consists of worksheets, each of which is a spreadsheet. If necessary, you can add worksheets or remove them from the book in the book. Button scrolling shortcuts scroll through the labels of the workbook. The extreme buttons scroll through the first and last labels of the workbook. Internal buttons scroll to the previous and next shortcut to the workbook.

Basic concepts of the spreadsheet: column header, line heading, cell, cell name, selection marker, fill marker, active cell, line of formulas, field name, active area of ​​the letter.

The workspace of the spreadsheet consists of rows and columns with their names. Line names are their numbers. Line numbering starts with 1 and ends with the maximum number set for this program. Column names are the letters of the Latin alphabet, originally from A to Z, then from AA to AZ, BA to BZ, and so on.

The maximum number of rows and columns is determined by the features of the program used and the size of the computer's memory, for example, in the Excel spreadsheet 256 columns and more than 16 thousand rows.

The intersection of a row and a column forms a table element that has its own unique address. In order to specify cell addresses, references are used in formulas (for example, A6 or D8).

The cell - the area defined by the cross section of the column and the row of the spreadsheet, has its own unique address. The address of the cell is determined by the name (number) of the column and the name (number) of the line, at the intersection of which is a cell, for example A10. Link is an indication of the address of the cell. Active cell is a highlighted cell whose name is displayed in the name field. The allocation marker is called a semidouble frame around the selected cell. The fill marker is a black square in the lower right corner of the highlighted cell.

The active area of ​​a sheet is an area containing the entered data. In spreadsheets, you can work with individual cells, or with groups of cells that form a block. Block of cells - a group of adjacent cells, determined by the address.

The address of the block of blocks is given by specifying the references of the first and the last of its cells, between which the separator character is put - a colon. If the block has a rectangle, its address is given by the addresses of the left upper and lower lower cells in the block. The block of cells used can be indicated in two ways: either the task from the keyboard of the source and the final cell addresses of the block, or by selecting the corresponding part of the table with the left mouse button. Example cell and block address assignments:

1. The address of the cell, located at the intersection of the column F and line 9, is expressed by the link F9;
2. address of the block formed as part of line 1, - B1: E1;
3. address of the block formed in the form of column C, - C1: C21;
4. The address of the block formed in the form of a rectangle is A3: G10

Working with files

When saving a working book, the dialog box "Save document" opens. In this window you must specify: file name, file type, select disk and folder where the working book will be stored. Thus, a book with incoming work sheets in it is stored in a folder on a disk as a separate file with a unique name. Book files have an xls extension.

To open a workbook, you must select the File / Open command or click on the Open button on the standard toolbar. Excel will display the dialog "Open Document" in it you can select the desired file and click on the Open button.

In order to close the workbook, select the File / Close command, which will close the workbook. To exit Excel, you must select the File / Exit command, or click on the close button in the right side of the title bar of the application window.

5. Self-checking

1. What is the difference between interpolation and approximation?
2. What is the essence of the method of least squares of linear approximation?