# New Approach to Fractal Approximation of Vector-Functions

Authors: Konstantin Igudesman; Marsel Davletbaev; Gleb Shabernev
Journal: Abstract and Applied Analysis
 (2015)

---

## Abstract

This paper introduces new approach to approximation of continuous vector-functions and vector sequences by fractal interpolation vector-functions which are multidimensional generalization of fractal interpolation functions. Best values of fractal interpolation vector-functions parameters are found. We give schemes of approximation of some sets of data and consider examples of approximation of smooth curves with different conditions.


---

## Body

## 1. Introduction

It is well known that interpolation and approximation are an important tool for interpretation of some complicated data. But there are multitudes of interpolation methods using several families of functions: polynomial, exponential, rational, trigonometric, and splines to name a few. Still it should be noted that all these conventional nonrecursive methods produce interpolants that are differentiable a number of times except possibly at a finite set of points. But, in many situations, we deal with irregular forms, which can not be approximate with desired precision. Fractal approximation became a suitable tool for that purpose. This tool was developed and studied in [1–3].We know that such curves as coastlines, price graphs, encephalograms, and many others are fractals since their Hausdorff-Besicovitch dimension is greater than unity. To approximate them, we use fractal interpolation curves [1] and their generalizations [4] instead of canonical smooth functions (polynomials and splines).This paper is multidimensional generalization of [5]. In Section 2, we consider fractal interpolation vector-functions which depend on several matrices of parameters. Example of such functions is given. In Section 3, we set the optimization problem for approximation of vector-function from L2 by fractal approximation vector-functions. We find best values of matrix parameters by means of matrix differential calculus. Section 4 illustrates some examples.


## 2. Fractal Interpolation Vector-Functions

Let[a,b]⊂R be a nonempty interval; let 1<N∈N and {(tn,xn)∈[a,b]×RM∣a=t0<t1<⋯<tN-1<tN=b} be the interpolation points. For all n=1,N¯, consider affine transformation(1)An:RM+1⟶RM+1,Antx≔an0cnDntx+enfn.Henceforth, small bold letters denote columns (rows) of length M and big bold letters denote matrices of M×M.Require that for alln the following conditions hold true:(2)An(t0,x0)=(tn-1,xn-1),An(tN,xN)=(tn,xn).Then, (3)ant0+en=tn-1,antN+en=tn,cnt0+Dnx0+fn=xn-1,cntN+DnxN+fn=xn.Solving the system, we have(4)an=tn-tn-1b-a,en=btn-1-atnb-a,cn=xn-xn-1-DnxN-x0b-a,fn=bxn-1-axn-Dnbx0-axNb-a,where matrices {Dn}n=1N are considered as parameters.Remark 1.
Notice that∑n=1Nan=1.Also notice that for alln operator An takes straight segment between (t0,x0) and (tN,xN) to straight segment which connects points of interpolation (tn-1,xn-1) and (tn,xn).LetK be a space of nonempty compact subsets of RM+1, with Hausdorff metric. Define the Hutchinson operator [6] (5)Φ:K⟶K,Φ(E)=⋃n=1N‍AnE.By the condition (2) Hutchinson operator Φ takes a graph of any continuous vector-function on segment [a,b] to a graph of a continuous vector-function on the same segment. Thus, Φ can be treated as operator on the space of continuous vector-functions Ca,bM.For alln=1,N¯, denote(6)pn:a,b⟶tn-1,tn,pnt≔ant+en,qn:a,b⟶RM,qn(t)≔cnt+fn.In (1), substitute x to vector-function g(t). We have that Φ acts on (C[a,b])M according to(7)Φgt=∑n=1N‍qn∘pn-1t+Dng∘pn-1tχ[tn-1,tn](t).Suppose that we consider all matricesDn as linear operators on RM. Furthermore, they are contractive mappings; that is, constant c∈[0,1) exists such that for all v,w∈RM and n=1,N¯ we have(8)Dnv-Dnw≤cv-w.Then, from (7), it follows that operator Φ is contraction with contraction coefficient c on Banach space ((C[a,b])M,·∞), where gt-ht∞≔sup⁡{t∈[a,b]:gt-ht}. By the fixed-point theorem, there exists unique vector-function g⋆∈(C[a,b])M such that Φg⋆=g⋆ and for all g∈(C[a,b])M we have (9)limk→∞Φk(g)-g⋆∞=0.Function g⋆ is called fractal interpolation vector-function. It is easy to notice that if g∈(C[a,b])M, g(t0)=x0, and g(tN)=xN, then Φ(g) passes through points of interpolation. In this case functions Φk(g) are called prefractal interpolation vector-functions of order k.Example 2.
Figure1 shows fractal interpolation vector-function of plane. Here t0=-1, t1=0, and t2=1 and x0=(1,-1), x1=(0,0), and x2=(1,1). Values of matrices D1 and D2 are(10)-1434-1412,-14-341412.Figure 1
Fractal interpolation vector-functiong⋆.


## 3. Approximation

Henceforth, we assume that for alln=1,N¯ linear operator Dn is contractive mapping with contraction coefficient c∈[0,1). We approximate vector-function g∈(C[a,b])M by fractal interpolation vector-function g⋆ constructed on points of interpolation {(tn,xn)}n=0N. Thus, we need to fit matrix parameters Dn to minimize the distance between g and g⋆.We use methods that have been developed for fractal image compression [7]. Denote Banach space of square integrated vector-functions on segment as (L2M[a,b],·2), where norm ·2 defines (11)g2=∫ab‍gt2dt.Then from (7) and (8) and Remark 1 it follows that for all g,h∈L2M[a,b](12)Φg-Φh22=∫ab‍Φg-Φh2dt=∑n=1N‍∫tn-1tn‍Dn∘g-h∘un-1t2dt=∑n=1N‍an∫ab‍Dn∘g-ht2dt≤∑n=1N‍anc2∫ab‍g-ht2dt=c2g-h22.Thus, Φ:L2Ma,b→L2Ma,b is a contractive operator and g⋆ is its fixed point.Instead of minimizingg-g⋆2 we minimize g-Φg2 that makes the problem of optimization much easier. The collage theorem provides validity of such approach [8].Theorem 3.
Let(X,d) be complete metric space and T:X→X is contractive mapping with contraction coefficient c∈0,1 and fixed point x⋆. Then (13)d(x,x⋆)≤d(x,T(x))1-cfor all x∈X.Considering (4) and (6), rewrite (7)(14)(Φg)(t)=∑n=1N‍(un(t)+Dn(g∘wn(t)-vn(t)))χ[tn-1,tn](t),where (15)unt=xn-xn-1t+tnxn-1-tn-1xntn-tn-1,vnt=xN-x0t+tnx0-tn-1xNtn-tn-1,wn(t)=(b-a)t+(tna-tn-1b)tn-tn-1.Thus, we minimize the functional(16)g-Φg22=∑n=1N∫tn-1tngt-unt-Dng∘wnt-vnt2dt.Lemma 4.
Letf,h∈L2M[a,b] be square integrated vector-functions. Suppose that matrix ∫ab‍hhTdt is nondegenerated. Matrix integration is implied to be componentwise. Then, the functional (17)Ψ:RM×M⟶R,Ψ(X)=∫ab‍f-Xh2dtreaches its minimum in X=∫ab‍fhTdt∫ab‍hhTdt-1.Proof.
To prove it, we use matrix differential calculus [9].
Consider(18)dΨX,U=d∫ab‍f-XhT(f-Xh)dtU=d∫ab‍fTf-hTXTf-fTXh+hTXTXhdtU=∫ab‍-hTUTf-fTUh+hTUTXh+hTXTUhdt=2∫ab‍-hTUTf+hTUTXhdt.Necessary condition of existence of functional Ψ extremum is dΨ(X,U)=0 for all U∈RM×M. Since there is U-linearity of functional dΨ(X,U), it is sufficient to prove dΨ(X,U)=0 only for matrices U that consist of M2-1 zeros and one unity. Therefore, we have M2 expressions for finding coefficients of matrix X. In matrix form these expressions are as follows: (19)∫ab‍fhTdt=∫ab‍XhhTdt,from which (20)X=∫abfhTdt∫ab‍hhTdt-1.
Hence,(21)d2Ψ(X,U)=2∫ab‍hTUTUhdt=2∫ab‍Uh2dt≥0,and then functional Ψ is convex one. Thus, the value X is absolute minimum of Ψ.From Lemma4, it follows that functional (16) reaches minimum when(22)Dn=∫tn-1tn‍gt-untg∘wnt-vntTdt·∫tn-1tn‍(g∘wn(t)-vn(t))g∘wnt-vntTdt-1.Example 5.
Let us approximate vector-functiong(t)=(t2,t3) on segment [-1,1] by the fractal interpolation vector-function constructed on values of g(t) in points t0=-1,  t1=0, and t2=1 and x0=(1,-1),  x1=(0,0), and x2=(1,1) (see Figure 2). Then, (23)a1=a2=12,e1=-12,e2=12,u1=-t,t,u2=t,t,v1=1,1+2t,v2=1,-1+2t,w1=1+2t,w2=-1+2t2.
CalculateD1, D2 according to formula (22) as follows: (24)D1=140-3818D2=1403818.
Apply affine transformations from (1) to vector {t,t2,t3}(25)A1tt2t3=1200-1214038-3818tt2t3+-1214-18A1tt2t3=t2-12t24-t2+14t38-3t28+3t8-18A1tt2t3=t-12t-122t-123,A2tt2t3=120012140383818tt2t3+121418A1tt2t3=t2+12t24+t2+14t38+3t28+3t8+18A1tt2t3=t+12t+122t+123.Thus, Φ(g)=g and g=g⋆.Figure 2
Vector-functiong(t)=(t2,t3) and fractal interpolation vector-function g⋆ completely identical.


## 4. Discretization and Results

In this section, we approximate discrete dataZ={(zm,wm)}k=0K, a=z0<z1<⋯<zK=b by fractal interpolation vector-function g⋆ constructed on points of interpolation X={(ti,xi)}i=0N, a=t0<t1<⋯<tN=b, N≪K. Assume that X⊂Z. We fit matrix parameters Dn to minimize functional (26)∑k=0K‍wk-g⋆zk2.It is necessary to use results of previous section. ApproximateZ by constant piecewise vector-function g:a,b→RM. More precisely gz=wk, where zk,wk∈Zzk is the nearest approximation neighbor of z. By substituting integrals in (22) to discretization points sums we obtain(27)Dn=∑zk∈tn-1,tn‍gzk-unzkg∘wnzk-vnzkT·∑zk∈tn-1,tn‍g∘wnzk-vnzkvvvvvvvvvvvvv·g∘wnzk-vnzkT∑zk∈tn-1,tn‍-1,vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvn=1,N¯.It is sufficient to apply (1) for constructing fractal interpolation vector-function after we find Dn.Consider several examples of approximation of discrete data.Example 6.
Let us approximate vector-functiong(t)=(t(t-2),(t-1)2(t+1)2), where t∈[-3,3]. Figure 3 shows the results. Here, we have two pictures; the first one illustrates initial vector-function and its approximation with 3 points and the second one with 4 points, where two functions are nearly identical.
In this case affine transformations (1) have the following form: (28)A1tx1x2=0.500-0.88420.0943-0.1045-0.1038-0.05300.2287tx1x2+00.73205.3989,A2tx1x2=0.5003.46020.7065-1.5549-0.45540.1504-0.2847tx1x2+0.7510.88758.1844.Figure 3
Approximation of vector-functiong(t)=(t(t-2),(t-1)2(t+1)2) by fractal interpolation function g⋆ with three (a) and four (b) points of interpolation correspondingly.
(a)
(b)Remark 7.
Vectorscn in matrices of affine transformations (1) equal 0 (like in previous example). It means that fractal interpolation vector-function can be treated as attractor of classical affine IFS in RM.Example 8.
Next example is devoted to a circleg(t)=(cos⁡t,sint), t∈[0,2π]. Figure 4 shows the results. Here we also have two pictures; the first one illustrates initial vector-function and its approximation with 3 points and the second one with 5 points.
In this case affine transformations (1) have the following form: (29)A1tx1x2=0.500-0.31800.00060.2128-0.0013-0.5686-0.0038tx1x2+00.99930.5686,A2tx1x2=0.5000.3181-0.0053-0.21280.00400.56860.0020tx1x2+3.151-0.9945-0.5770.Figure 4
Approximation of vector-functiong(t)=(cos⁡t,sint) by fractal interpolation function g⋆ with three (a) and five (b) points of interpolation correspondingly.
(a)
(b)Example 9.
Spiral of Archimedesg(t)=(tcos⁡t,tsint), t∈[0,5π], where the scheme is equal to the examples above, but here we use far more points of interpolation, as illustrated in Figure 5.Figure 5
Approximation of vector-functiong(t)=(tcos⁡t,tsint), t∈[0,5π], by fractal interpolation function g⋆ with twelve (a) and seventeen (b) points of interpolation correspondingly.
(a)
(b)Example 10.
Figure6 shows approximation of vector-function g(t)=(cos⁡(1.5t),sin(t)), t∈[0,12π], by fractal interpolation vector-function with sixteen points of interpolation.Figure 6
Approximation of vector-functiong(t)=(cos⁡(1.5t),sin(t)) by fractal interpolation function g⋆.Example 11.
The example illustrates approximation of graph of Weierstrass functionω(x)=∑n=0∞(1/2)n‍cos⁡(2π4nx) (Figure 7) by fractal interpolation vector-function.
This example is taken from [10], where fractal approximation is used for approximate calculation of box dimension of fractal curves.Figure 7
Weierstrass function (blue one) and approximating vector-function (red one).


## 5. Conclusion

In this paper, we have introduced new effective method of approximation of continuous vector-functions and vector sequences by fractal interpolation vector-functions, which are affine transformations with matrix parameters. Parameter fitting was a crucial part of approximation process. We have found appropriate parameter values of fractal interpolation vector-functions and illustrate it with several examples of different types of discrete data.We assume that fractal approximation is highly promising computational tool for different types of data and it can be used in many ways, even in interdisciplinary fields, with a quite high precision that allows us to apply fractal approximation methods to a wide variety of curves, smooth and nonsmooth alike.



---

*Source: 278313-2015-07-26.xml*